Red-black tree visualizer

Type a key and press Insert or Delete. The tree updates, and the panel lists every step the algorithm took: where the key went, each recolouring, each rotation. Press Previous and Next, or click a step, to see the tree at that moment, with the nodes involved outlined. The five red-black rules are checked after every operation.

• Press Insert 1 to 10 in order. A plain binary search tree would become a chain ten nodes long; this one stays 5 levels deep.
• Insert 5 into the starting tree: a case 3 rotation. Then insert 4: a case 1 recolouring pushes the problem two levels up, where a case 3 rotation fixes it.
• Delete the root and follow the deletion fix-up, the harder half of the algorithm.
• Turn on Show NIL leaves to see the empty black leaves that the rules count.

The code follows the insertion and deletion procedures in Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. It was checked by 80,000 random insertions and deletions against a sorted set, verifying the five rules and the key order after every one.

A red-black tree is a binary search tree in which every node also stores a colour, red or black, and the colours must follow a few rules. A binary search tree keeps smaller keys to the left and larger keys to the right, so finding a key takes as many steps as the tree is tall. An ordinary one can grow lopsided: inserting keys in sorted order produces a chain, and lookups become as slow as scanning a list. The red-black rules prevent that. After every insertion or deletion, the tree repairs any broken rule by recolouring nodes and performing a few rotations, which keeps its height logarithmic in the number of keys.

Red-black trees are the most common balanced search tree in standard libraries, because they guarantee O(log n) for every operation while doing little restructuring on updates.

1. Every node is either red or black.
2. The root is black.
3. Every leaf is black. In this formulation the leaves are the empty NIL children, not nodes holding keys.
4. If a node is red, both its children are black. So two red nodes are never adjacent on a path.
5. For every node, all paths from it down to its NIL leaves contain the same number of black nodes. This number is the node's black height.

Some texts drop rule 3 and count black heights without the NIL leaves, or allow a red root; these are differences of bookkeeping, not of the structure.

Rule 5 means every path from the root to a leaf has the same number of black nodes, say b. Rule 4 means red nodes cannot sit next to each other, so a path has at most one red node for each black one, and its length is between b and 2b. The shortest path is therefore at least half as long as the longest.

A subtree whose root has black height b contains at least 2^b − 1 keys (it contains a complete binary tree of black nodes). Putting the two facts together, a red-black tree with n keys has height at most 2 log₂(n + 1). Inserting 1 to 15 in order, the worst case for a plain binary search tree, gives this tree a height of 6, against a bound of 8:

A rotation changes the shape of a binary search tree without changing the order of its keys. A left rotation at node x moves its right child y up into x's place, makes x the left child of y, and hands y's old left subtree to x as its new right subtree. A right rotation is the mirror image. Each takes constant time, since only three links change. Rotations, together with recolouring, are all a red-black tree uses to rebalance.

Insert the new key as in a plain binary search tree, as a leaf, and colour it red. A red node adds nothing to any path's black count, so rule 5 still holds. The only rule that can break is rule 4, if the new node's parent is also red (or rule 2, if the new node is the root). The fix depends on the new node's uncle, its parent's sibling:

• Case 1, the uncle is red. Colour the parent and the uncle black and the grandparent red. Black counts are unchanged below the grandparent, but the grandparent may now be a red node with a red parent, so repeat the check two levels up.
• Case 2, the uncle is black and the new node is an inner child (a right child of a left child, or the reverse). Rotate at the parent so the two red nodes form a straight line, which turns the situation into case 3.
• Case 3, the uncle is black and the new node is an outer child. Colour the parent black and the grandparent red, then rotate at the grandparent. The parent takes the grandparent's place, black, with two red children, and the fix-up ends.

Finally colour the root black. Case 1 can repeat up the tree, but it only recolours, and cases 2 and 3 run at most once, so an insertion performs at most two rotations.

Inserting 10, 20, 30, 15, 25, 5, 1 into an empty tree, as the simulator does it:

Deletion starts like deletion in a plain binary search tree: a node with at most one child is replaced by that child; a node with two children is replaced by its successor, the smallest key in its right subtree. If the node that disappeared from its position was red, nothing else is needed. If it was black, every path through that spot is now one black node short, which breaks rule 5. The fix-up treats the node that took its place, x, as carrying an extra black, and looks at x's sibling w:

• Case 1, the sibling is red. Recolour and rotate at the parent so that the sibling becomes black, then continue with one of the other cases.
• Case 2, the sibling and both its children are black. Colour the sibling red, which removes a black from its side too, and move the extra black up to the parent.
• Case 3, the sibling is black, its near child red and its far child black. Swap colours and rotate at the sibling, turning this into case 4.
• Case 4, the sibling is black and its far child red. Recolour and rotate at the parent. The extra black is absorbed, and the fix-up ends.

If x is red, or reaches the root, colouring it black finishes the job. Deletion performs at most three rotations. Here is the simulator deleting 10 from the tree built above:

A red-black tree is a binary encoding of a 2-3-4 tree, a B-tree in which each node holds one, two or three keys. Take a black node together with its red children, and you have one 2-3-4 node: a black node alone holds one key, with one red child two keys, with two red children three keys. Rule 5 says every 2-3-4 leaf is at the same depth, as in any B-tree, and case 1 of insertion, recolouring a black node with two red children, is exactly splitting a full 2-3-4 node.

In 2008 Robert Sedgewick published the left-leaning red-black tree, which allows red links only on the left. That removes most of the symmetric cases and makes the code much shorter, at the price of a few more rotations. It corresponds to a 2-3 tree when 4-nodes are split on the way down.

• C++ standard library implementations (libstdc++, libc++ and Microsoft's) use red-black trees for std::map, std::set and their multi- variants.
• Java's TreeMap and TreeSet are red-black trees, and since Java 8 a HashMap bucket that collects eight or more entries is converted into a small red-black tree.
• .NET's SortedSet<T> and SortedDictionary are built on a red-black tree.
• The Linux kernel has a shared red-black tree library, lib/rbtree.c, used by the process scheduler to order runnable tasks, by epoll, by timers and by many file systems.

Rudolf Bayer described the structure in 1972 as the symmetric binary B-tree, a binary form of the B-trees he had invented. In 1978 Leonidas Guibas and Robert Sedgewick recast it with red and black colours in "A Dichromatic Framework for Balanced Trees". Sedgewick has said the colours were chosen partly because red looked best on the colour laser printer available to them at Xerox PARC. Introduction to Algorithms (first edition 1990) made the five-property formulation and its insertion and deletion cases the standard way the structure is taught.