What is the height of a redblack tree with n nodes ExplainSo

What is the height of a red-black tree with n nodes?
Explain.

Solution

Red-Black tree is a binary search tree with following constraints:

1.Every node is either red or black node.

2.Every root is a black node.

3.Every red node must contain either zero or one black nodes.

4.Every root-null path must have same number of black nodes.

The maximum number of black nodes in any root-null path is restricted by the number of nodes in the shortest root-null path.

Suppose the shortest root-null path has depth k,

then there will be k+1 nodes in a tree with depth k, and there will be a complete and full subtree of depth k.

Suppose the full and complete binary subtree with n nodes then we can say that

k+1= log2(n+1) from the fact n=2k+1-1

Maximum height =maximum red nodes+ maximum black nodes  

     = log2(n+1)+ log2(n+1)

    = 2log2(n+1)

With this it is proved that the height of the red-black tree is O(log n).