What is the maximum degree of imbalance in a red black tree ? Is it height/2?

Question

The goal of the red-black tree structure is to have a tree that is only approximately balanced. What is the maximum degree of imbalance possible?

I think it would be 1 since the maximum diference occur if we have red nodes at the one previous to the leaf ?

Answer 1

One property of red-black trees is that the number of black nodes on any root-to-leaf path is constant. This constant is called the black height of the tree.

Another property is that red nodes cannot have red children. That means that if a red-black tree has a black height of , then the shortest possible root-to-leaf path will have (all black) nodes (including a black root), and the longest possible root-to-leaf path in the same tree (so also with a black root) will have 2 nodes, where black and red nodes are alternating, ending in a red (real) leaf.

For example, this is a red-black tree with black height equal to 3:

              __B__
             /     \
           _r_      B
          /   \    / \
         B     B  B   B
        / \   / \
       r   B B   B
      / \
     B   B
    /
   r

The longest root-to-leaf path cannot be longer, except if we add a red root at the top, but this will then also make the shortest path longer.

Finally, we should note that the definition of height counts edges from root-to-leaf, while black height counts nodes.

So if the height of a black-red tree is given as ℎ, then all root-to-leaf paths will have a length (counting edges) of at least ⌈(ℎ+1)/2⌉−1, i.e. ⌊ℎ/2⌋ (and at most ℎ)