Red-Black Tree

Red Black Tree is a type of balanced binary search tree. It adds a bit to stand for the color: RED or BLACK, of each node.

Formal Def:

A Red Black Tree is a type of binary search tree that follows the properties below:

1. Each node is either RED or BLACK

2. The root is BLACK

3. All leaf nodes (NIL) are BLACK

4. If a node is RED, both of its children are BLACK

5. Every path from a node to its leaves contains the same number of BLACK nodes (Def: the number of black nodes from a chosen node 𝓍 to a NIL leaf (node 𝓍 is not included) is called the black-height (bh(𝓍)) of such node, the number of black nodes from root to any NIL leaves is the black-height of the total red-black tree)

Height Guarantee

Formal Claim:

For every red-black tree with 𝓃 nodes, its height 𝒽 ⩽ 2 ⋅ log2 (n + 1).

Proof:

First, there are at least 2bh(x) - 1 number of internal nodes rooted from node x.

By simple induction, the base case: if height of tree x is 0, then there is 20 - 1 = 0; for tree with height more than 0 with both child nodes, there are at least 2bh(x) - 1 - 1 internal nodes for each child node. Therefore, a rooted tree from x has at least 2 * (2bh(x) - 1 - 1) + 1 = 2bh(x) - 1.

Presumably, for a given tree with height 𝒽, any paths leading from root to leaves have at least half of the nodes are black, in other words, the bh(root) ⩾ 𝒽/2; then

n ⩾ 2𝒽/2 - 1, 𝒽 ⩽ 2 log(n+1)

guarantee holds, proof ends.