|Invented by||Bayer (1972), Guibas, Sedgewick (1978)|
|Variations:||left leaning red-black tree: when mimicking a 3-node, the red node is a left child|
|Disadvantages:||hard to implement|
Correspondence with 2-3-4 trees
Red-black trees are sometimes defined with these three invariants:
- The root is black.
- Children of red nodes are black.
- Every path from root to leaf has the same number of black nodes.
Where the hack did these come from?
Well, a red-black tree is just a binary search tree representation of a 2-3-4 tree.
Recall that in 2-3-4 tree, all nodes contain 1, 2, or 3 keys and have 2, 3, or 4 children, respectively.
In a red-black tree,
- a 2-node corresponds to a black node with black children,
- a 3-node corresponds to a black node with one red child,
- and a 4-node corresponds to a black node with two red children.
A red-black tree is just a special case for B trees of order 4, a.k.a. 2-3-4 tree.
The invariants make sure that this correspondence holds. Namely, the first two invariants make sure, that if we take a black node together with its red children and call it a “supernode”, then since red nodes can only have black children, these supernodes consist of 1, 2, or 3 regular nodes and their children are again supernodes. Invariant #3 says that each path from root to leaf goes through the same number of supernodes. This corresponds to the invariant of 2-3-4 trees (or B-trees in general) that all the leaves must be at the same level.
Nodes we insert are red so the only invariant we might break is #2 (red node with red parent). Let \(x\) be a red node with red parent \(y\). There are 3 cases we need to consider, however, if we keep in mind the correspondence with 2-3-4 tree, it’s actually easy.
Case 1: Red uncle
Uncle = parent’s brother. In the figure below, \(x\)’s uncle is node \(w\) (it’s the sibling of \(x\)’s parent, \(y\)). If this node is red, it means that the supernode \((x,y,z,w)\) overflowed. We simply recolor the nodes as follows:The case when \(x\) is a right child is the same:
(You can think of it as pushing black from \(z\) down onto its children \(y\) and \(w\).)
Note that this corresponds exactly to splitting operation in 2-3-4 trees:
The 5-node \((x,y,z,w)\) is split into 3-node \((x,y)\) and 2-node \(w\) and \(z\) is moved to the supernode above. Now parent of \(z\) might be red, so we need to deal with that recursively. There might be a cascade of recolorings similar to a cascade of splittings in a 2-3-4 tree.
Case 2, 3: Black uncle
If \(x\)’s uncle is black (\(\delta\) in the figures below), the \((x,y,z)\) supernode is a 4-node, which is OK, we just need to rotate it so it has a proper shape:
Note that in these cases, we can stop.
A red-black tree insertion may involve several (at most \(O(\log n)\)) recolorings, but only 2 rotations at most.
- R. Sedgewick. Left-leaning red-black trees. In Dagstuhl Workshop on Data Structures, page 17, 2008. [bib] [pdf]
- R. Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta informatica, 1(4):290-306, 1972. [bib]
- L.J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Foundations of Computer Science, 1978., 19th Annual Symposium on, pages 8-21. IEEE, 1978. [bib]
- R.E. Tarjan. Updating a balanced search tree in O(1) rotations. Information Processing Letters, 16(5):253-257, 1983. [bib]
- A. Andersson, C. Icking, R. Klein, and T. Ottmann. Binary search trees of almost optimal height. Acta Informatica, 28(2):165-178, 1990. [bib] [pdf]