Maximum height of a node in a red-black tree-CodePudding

If we have a node in a red-black tree with a black height of 3, what is the maximum height allowed for the node?

CodePudding user response：

A red black tree has a max height of 2 * log(n 1) so if the number of nodes is 15 , then the max height should be 2 * log(16) or 8

Interesting points about Red-Black Tree:

Black height of the red-black tree is the number of black nodes on a path from the root node to a leaf node.
Leaf nodes are also counted as black nodes. So, a red-black tree of height h has black height >= h/2.
Height of a red-black tree with n nodes is h<= 2 log2(n 1). All leaves (NIL) are black.
The black depth of a node is defined as the number of black nodes from the root to that node i.e the number of black ancestors.
Every red-black tree is a special case of a binary tree.

Black Height of a Red-Black Tree :

Black height is the number of black nodes on a path from the root to a leaf. Leaf nodes are also counted black nodes. From the above properties 3 and 4, we can derive, a Red-Black Tree of height h has black-height >= h/2.

Every Red Black Tree with n nodes has height <= 2Log2(n 1) This can be proved using the following facts:

For a general Binary Tree, let k be the minimum number of nodes on all root to NULL paths, then n >= 2k – 1 (Ex. If k is 3, then n is at least 7). This expression can also be written as k <= Log2(n 1).
From property 4 of Red-Black trees and above claim, we can say in a Red-Black Tree with n nodes, there is a root to leaf path with at-most Log2(n 1) black nodes.
From property 3 and 5 of Red-Black trees, we can claim that the number of black nodes in a Red-Black tree is at least ⌊ n/2 ⌋ where n is the total number of nodes.
From the above points, we can conclude the fact that Red Black Tree with n nodes has height <= 2Log2(n 1)

CodePudding user response：

To maximise the height of that node, you'll want to create the longest downwards path possible with only 3 black nodes in it (excluding the starting node). As in red-black trees a red node cannot have a red child, the best you can do is to alternate the colors on such a path. Also, the path must end with a black node, since all (NIL) leaves are black. So the longest path with 3 black nodes is:

node (black, but not counted in "black height")
   \
   red 
     \ 
     black #1
       \
       red
         \
         black #2
           \
           red
             \
             black #3/NIL

The height (= length of path) is 6. It cannot be longer. So that is the maximum height of a node with a black height of 3. In general the maximum height of a node is the double of its black height.