Deriving time complexity of Binary tree and AVL tree, step
by step.
- 4 Answers
- 15375 Views
- NetApp, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / tilak chandan
Lemma: A subtree rooted at node v has at least 2bh(v) − 1 internal nodes.
Proof of Lemma (by induction height):
Basis: h(v) = 0
If v has a height of zero then it must be null, therefore bh(v) = 0. So:
2bh(v) − 1 = 20 − 1 = 1 − 1 = 0
Inductive Step: v such that h(v) = k, has at least 2bh(v) − 1 internal nodes implies that v' such that h(v') = k+1 has at least 2bh(v') − 1 internal nodes.
Since v' has h(v') > 0 it is an internal node. As such it has two children each of which have a black-height of either bh(v') or bh(v')-1 (depending on whether the child is red or black, respectively). By the inductive hypothesis each child has at least 2bh(v') − 1 − 1 internal nodes, so v' has at least:
2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1
internal nodes.
Using this lemma we can now show that the height of the tree is logarithmic. Since at least half of the nodes on any path from the root to a leaf are black (property 4 of a red black tree), the black-height of the root is at least h(root)/2. By the lemma we get:
Therefore the height of the root is O(log(n)).
| Is This Answer Correct ? | 2 Yes | 1 No |
Answer / pudwallis gudzinsky
I do not know the answer either. In fact, I do not believe
that a question was asked. Therefore, I feel that this is
a trick non-question. If the question was "Do I like tater
tots?" Indeed the answer would be a resounding Yes and I
am 100 percent certain that this answer is correct.
If there are girls available in the room, I would not like
strike with them.
| Is This Answer Correct ? | 5 Yes | 22 No |
Answer / haresh
Actually i was searching for the same answer as i dont know
what the answer is.. But yah if there are girls in ur room i
will be happy striking with them lol
| Is This Answer Correct ? | 1 Yes | 19 No |
Answer / ssss ss
I do not know what the answer is .I am subhani and you are
not my friend .However I do not the answer.But you do not
know the answer.You have already told me that i have already
strike with the girls available in the room.
| Is This Answer Correct ? | 6 Yes | 34 No |
Deriving time complexity of Binary tree and AVL tree, step by step.
what mean void creat_object?in public class in this code class A{ public: int x; A(){ cout << endl<< "Constructor A";} ~A(){ cout << endl<< "Destructor A, x is\t"<< x;} }; void create_object(); void main() { A a; a.x=10; { A c; c.x=20; } create_object(); } void create_object() { A b; b.x=30; }
write a program to sort 'n' elemnts using bubble sort
Min-Max Write an algorithm that finds both the smallest and largest numbers in a list of n numbers and calculate its complexity T(n).
1 Answers Infosys, Qatar University,
write a c program, using for loop, that accepts and odds two numbers. The output must be the sum and the addens. This should be repeated 5 times while the first number is decremented by one and the second number is incremented by 1.
Write a program that takes a 3 digit number n and finds out whether the number 2^n + 1 is prime, or if it is not prime find out its factors.
5 Answers ADP, Amazon, HCL, IBM, Infosys, Satyam, TCS, Vimukti Technologies,
i don't know about working of nested for loop can any one help me
A string of charaters were given. Find the highest occurance of a character and display that character. eg.: INPUT: AEGBCNAVNEETGUPTAEDAGPE OUTPUT: E
output for printf("printf");
Given 1 to n random number, find top 10 maximum numbers and explain the time complexity of the algorithm.
1. Write a program that performs the following. The user inputs a number and then enters a series of numbers from 1 to that number. Your program should determine which number (or numbers) is missing or duplicated in the series, if any. For example, if the user entered 5 as the initial number and then entered the following sequences, the results should be as shown. Input Sequence Output ---------------------- --------------- 1 2 3 4 5 Nothing bad However, if 7 were the high number, the user would see the results on the right for the following number entries: Input Sequence Output ---------------------- --------------- 1 3 2 4 5 Missing 6 Missing 7 And if 10 were the high number and the user entered the numbers shown on the left, note the list of missing and duplicate numbers: Input Sequence Output ---------------------- --------------- 1 2 4 7 4 4 5 10 8 2 6 Duplicate 2 ( 2 times) Missing 3 Duplicate 4 ( 3 times ) Missing 9
Show by induction that 2n > n2, for all n > 4.
2 Answers Karvy, Qatar University,
C Code 
