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)).

Code for Two Classes for Doing Gzip in Memory?

2807

---

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.)

4445

---

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!!!)

3268

---

how to diplay a external image of output on winxp by using c & c++,

2930

---

solve the problem in the programming language C++"if a five digit number is input through the keyboard.Write a program to calculate the sum of its digits(hint: use the modulus operator)

2930

---

---

Code for Method of Handling Factorials of Any Size?

2000

---

write a program that reads a series of strings and prints only those strings begging with letter "b"

2668

---

Given a table of the form: Product Sold on A 1/1/1980 B 1/1/1980 C 1/1/1980 A 1/1/1980 B 1/1/1980 C 2/1/1980 A 2/1/1980 There are 30 products and 10,000 records of such type. Also the month period during which sales happened is given to u. Write the program to display the result as: Product Month No. of copies A January 12 A February 15 A March 27 B January 54 B February 15 B March 10 C January 37

2188

---

how to write a program that opens a file and display in reverse order?

2561

---

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

2002

---

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?

2909

---

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; }

575

---

write a program to convert temperature from fa height into celcius and vise versa,use modular programming

2434

---

How can I Draw an ellipse in 3d space and color it by using graph3d?

2130

---

How to Split Strings with Regex in Managed C++ Applications?

3120

---