Deriving time complexity of Binary tree and AVL tree, step
by step.
Answer Posted / 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 |
Post New Answer View All Answers
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
1+1/2!+1/3!+...+1/n!
write a program to calculate the amount of investment after a period n years if the principal investors was p and interest is calculated using compound interest,formular=a=p(1+r)^n
how to take time as input in the format (12:02:13) from user so that controls remains between these columns?
how to diplay a external image of output on winxp by using c & c++,
find level of following tree (state, parent) " J,D I,D H,C E,B F,B G,C B,A D,A C,A A,& K,E L,E L,F M,F N,G O,H P,I P,H Q,I R,J S,K U,P T,L
Write a C++ program without using any loop (if, for, while etc) to print prime numbers from 1 to 100 and 100 to 1 (Do not use 200 print statements!!!)
Write a program that print in screen a tree with its height taken from user by entering number of 4 digits and find the odd numbers then calculate the sum of odd numbers so he get the height of tree?
Write a C/C++ program that connects to a MySQL server and displays the global TIMEZONE.
Write a (n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn-element array.)
What output does this program generate as shown? Why? class A { A() { cout << "A::A()" << endl; } ~A() { cout << "A::~A()" << endl; throw "A::exception"; } }; class B { B() { cout << "B::B()" << endl; throw "B::exception"; } ~B() { cout << "B::~B()"; } }; int main(int, char**) { try { cout << "Entering try...catch block" << endl; A objectA; B objectB; cout << "Exiting try...catch block" << endl; } catch (char* ex) { cout << ex << endl; } return 0; }
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; }
Question 1: Implement a base class Appointment and derived classes Onetime, Daily, Weekly, and Monthly. An appointment has a description (for example, “see the dentist”) and a date and time. Write a virtual function occurs_on(int year, int month, int day) that checks whether the appointment occurs on that date. For example, for a monthly appointment, you must check whether the day of the month matches. Then fill a vector of Appointment* with a mixture of appointments. Have the user enter a date and print out all appointments that happen on that date. *This Should Be Done IN C++
A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect
Create a program to read two random data set in two files named data1.txt and data2.txt manifold contains integer numbers, whereas data2.txt file contains the float type numbers. Simpanlahmasing each into 2 pieces of data that is an array of type integer array and an array of type float, then calculate the average numbers in the second array.