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 ) \).

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.

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.

(When logged in, completion status appears here.)