Key Points
2–3–4 Trees
- A 2–3–4 Tree allows three kinds of nodes:
- 2-nodes hold one value and have two children.
- 3-nodes hold two values and have three children.
- 4-nodes hold three values and have four children.
- Insertion in a 2–3–4 tree always happens at a leaf, by adding the new value to an existing leaf node. That insertion will turn a 2-node into a 3-node or a 3-node into a 4-node.
- To make sure that there is always room to insert new values, any time we pass a 4-node on the way down the tree during an insertion, we promote the middle value up into the node above it.
- 2–3–4 trees require more work at each node than a BST, but because they stay perfectly balanced (all leaves the same distance from the root), they have worst-case lookup and insert performance of \( \Theta( \log n ) \).
Red–Black Trees
- A Red–Black tree is a binary representation of a 2–3–4 tree.
- To convert a 4-node to a Red–Black representation, create a black node from the middle value. Then add two children for the left and right values, both as red nodes.
- To convert a 3-node to a Red–Black representation, create a black node from one of the two values. Then add a child for the other value as a red node.
- Because Red–Black trees are isomorphic with 2–3–4 trees, they also have \( \Theta( \log n ) \) worst-case performance for insert and lookup.
Rotation
- A fundamental operation for rearranging nodes in a BST.
- Can be implemented with a constant number of pointer reassignments (i.e., constant time):
- A child of the root of the subtree moves up to become the new root.
- The old root becomes the new root's child.
- The subtree “between” the two nodes becomes the old root's child.
- Rotations preserve the BST property.
Like these University of Washington CSE grad students (“The CSE Band”) from the early 2000s, we hope you're inspired by the beauty of Red–Black trees!.
(When logged in, completion status appears here.)