Interested to Buy Any Domain ? << Click Here >> for more details...
Deriving time complexity of Binary tree and AVL tree, step
by step.
- 4 Answers
- 16269 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 |
How to Split Strings with Regex in Managed C++ Applications?
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.
3 Answers TCS, Vimukti Technologies, Wipro,
Where now stands that small knot of villages known as the Endians, a mighty forest once stood. Indeed, legand has it that you could have stoodon the edge of the wood and seen it stretch out for miles, were it not for the trees getting in the way. In one section of the forest, the trees stood in a row and were of hight from 1 to n, each hight occurring once and once only. A tree was only visible if there were no higher trees before it in the row. For example, if the heights were 324165, the only visible trees would have been those of height 3,4 & 6. Write a Program that takes an array of integers representing the heights of the trees in the row as input and prints the list of the visible trees.
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
i really need help about this.. write a program to display the set of odd and even numbers separately. find the highest and lowest value of the given numbers.
Write an algorithm that receives a string and reverses it.
1.program to add any two objects using operator overloading 2.program to add any two objects using constructors 3.program to add any two objects using binary operator 4.program to add any two objects using unary operator
How reader and writer problem was implemented and come up with effective solution for reader and writer problem in case we have n readers and 1 writer.
swap prog
write a program using virtual function to find the transposing of a square matrix?
Min-Max Write an algorithm that finds both the smallest and largest numbers in a list of n numbers and with complexity T(n) is at most about (1.5)n comparisons.
10 Answers ABC, College School Exams Tests, ITC Infotech, Kyambogo University, Qatar University,
write a program that creates a sequenced array of numbers starting with 1 and alternately add 1 and then 2 to create the text number in the series , as shown below. 1,33,4,6,7,9,............147,148,150 Then , using a binary search , searches the array 100 times using randomly generated targets in the range of 1 to 150
C Code 
