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:
Each node is either RED or BLACK
The root is BLACK
All leaf nodes (NIL) are BLACK
If a node is RED, both of its children are BLACK
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.
Last updated