Red-Black Tree
Type of self-balancing binary search tree to ensure query operation time of $O(\log n)$.
Insertions and deletions also still run in $O(\log n)$ time.
Could be thought of as an implementation to the binary search tree ADT.
Table of contents
Properties
- Every node is either red or black.
- The root is black.
- Every leaf (NIL) is black.
- If a red node has children, then the children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
Internal Nodes
Since the leaves are all black, we generally simplify the tree to only have internal nodes.
There is a lemma that a red-black tree with $n$ internal nodes has a height of at most $2\log(n+1)$.
Black Height
To prove the above lemma, we introduce the concept of black height.
The black height of a node $x$ ($bh(x)$) is the number of black nodes in the simple path from $x$ to a leaf (includes the leaf but not $x$ itself).
So if $x$ is a leaf, then its black height is 0, because we don’t count the leaf itself even though it is black.
Although there are many paths to different leaves, this function is well-defined because of property 5 (each path have the same number of black nodes).
Isometry of 2-3-4 Trees
A 2-3-4 tree is a multiway search tree where every node has 2, 3, or 4 children (where each node has 1, 2, or 3 keys respectively).
In a Red-Black tree, if we absorb all red nodes into their parents (which are black), we get a 2-3-4 tree.
Therefore, a red-black tree is an isometry of a 2-3-4 tree.
Rotations
