Red-Black Trees

A red-black tree (RB-tree) is a type of self-balancing BST. It is complex, but has a good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the total number of elements in the tree.

  • In RB-trees, the leaf nodes are not relevant and do not contain data. A null child pointer can encode the fact that this child is a leaf.
  • Like BSTs, RB-trees allow efficient in-order traversals of elements.
  • The search time on a RB-tree results in O(log n) time.

Properties

A RB-tree is a BST where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on BSTs, the following additional requirements apply to RB-trees:

  1. A node is either red or black.
  2. The root is black.
  3. All leaves are black.
  4. Both children of every red node are black.
  5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

Example red-black tree: black root 13, red children 8 and 17, black nodes 1, 11, 15 and 25, red nodes 6, 22 and 27, and black NIL leaves under every node; every root-to-NIL path passes through the same number of black nodes

The above constraints enforce a critical property of RB-trees:

  • The longest path from the root to any leaf is no more than twice as long as the shortest path from the root to any other leaf in that tree.
  • The result is that the tree is roughly balanced.
  • Insertion, deletion, and search require worst-case time proportional to the height of the tree, the theoretical upper bound on the height allows RB-trees to be efficient in the worst case.

To see why these properties guarantee this, it suffices to note that no path can have two red nodes in a row, due to property 4. The shortest possible path has all black nodes, and the longest possible path alternates between red and black nodes. Since all maximal paths have the same number of black nodes, by property 5, this shows that no path is more than twice as long as any other path.

Insertions and removals are quite complex in a RB-tree in order to keep the properties.

Insertion

Insertion begins by adding the node as any BST insertion does and by coloring it red. It's a red inner node with two black leaves.

  • Property 3 (all leaves are black) always holds.
  • Property 4 (both children of every red node are black) is threatened only by adding a red node, repainting a black node red, or a rotation.
  • Property 5 (all paths have same number of black nodes) is threatened only by adding a black node, repainting a red node black (or vice versa), or a rotation.

In the following description, we have labels N (current node), P (N's parent), G (N's grandparent), and U (N's uncle).

  • Case 1: N is root. It's repainted black to satisfy property 2.
  • Case 2: P is black. Property 4 (children of red are black) is not violated. Property 5 holds since N has two black leaf children, but N is red.
  • Case 3: if both P and U are red, repaint them black and repaint G red. Recursively insert G.

Case 3: parent P and uncle U are both red; P and U are repainted black and grandparent G red, N stays red

  • Case 4: P is red, but U is black; N is the right child of P, and P is the left child of G. Perform left rotation on P. Then go to Case 5.

Case 4: red N is the right child of red P; a left rotation at P makes N the left child of G and P the left child of N, turning it into case 5

  • Case 5: right rotation. Repaint G and P.

Case 5: red N is the left child of red P; a right rotation at G makes P the subtree root with children N and G, P is repainted black and G red

For deletion on a RB-Tree, please see the Wikipedia link for details.

Let's try it out with the following sequence of values: 14, 17, 11, 7, 53, 4, 13, 12, and 8.

Why the colour rules keep the tree balanced

The rules look arbitrary, but together they force the tree to be roughly balanced. Every path from the root down to a leaf contains the same number of black nodes — the tree's black height — and no path may contain two red nodes in a row. So the longest path possible, alternating black and red, is at most twice the length of the shortest path possible, which is all black. That bounds the height at 2 log2(n + 1), and every operation here walks a single root-to-leaf path, so all of them take O(log n) time.

Repairing the tree afterwards is cheap, and this is the property that makes red-black trees popular: an insertion needs at most two rotations and a deletion at most three, however large the tree. Recolouring can travel all the way up to the root, but recolouring is trivial; rotations, which move whole subtrees around, are the expensive part, and their number is bounded by a constant.

Red-black or AVL?

Both are self-balancing binary search trees, and both give O(log n) search, insert and delete. They differ in where they spend the effort:

  • An AVL tree is held more strictly in balance: its height is at most about 1.44 log2 n, against 2 log2 n here. Shorter tree, slightly faster lookups.
  • A red-black tree rebalances more cheaply. An AVL deletion can trigger rotations at every level on the way back up — O(log n) of them — where a red-black deletion never needs more than three.

So AVL suits workloads that are mostly reads, and red-black suits structures that are written to constantly. Kernels and standard libraries cannot know the workload in advance, and they almost all pick red-black.

Where red-black trees are used

This is not a structure that stayed in the textbook. If you have ever used an ordered map in C++ or Java, you have used a red-black tree.

  • Ordered containers in standard libraries. C++'s std::map, std::set, std::multimap and std::multiset are red-black trees in libstdc++, libc++ and MSVC alike. So are Java's TreeMap and TreeSet, and .NET's SortedDictionary and SortedSet. This is probably the most heavily executed red-black tree code in the world.
  • Java's HashMap. Since Java 8, a hash bucket that accumulates about eight colliding entries is converted into a red-black tree, which pulls the worst case back from O(n) to O(log n). It was added specifically to blunt attacks that feed a server keys chosen to collide.
  • The Linux kernel, which carries one shared implementation in rbtree.h and uses it everywhere: the process scheduler keeps runnable tasks ordered by virtual runtime, so the next task to run is simply the leftmost node; epoll stores the set of watched file descriptors; high-resolution timers are ordered by expiry; and the ext3/ext4 directory index, the I/O schedulers, futexes and the packet schedulers all use one.
  • Interval trees and order-statistic trees. A red-black node tolerates a little extra bookkeeping cheaply, so augmenting each node answers questions a plain tree cannot: which of the stored intervals overlap this one, or what is the kth smallest element, both in O(log n).
  • Computational geometry. Sweep-line algorithms, such as Bentley-Ottmann for finding every intersection among a set of line segments, keep the currently active segments in a balanced tree ordered by where they cross the sweep line.

Two things are worth knowing about the limits. First, a hash table beats any tree at plain lookup; you reach for a red-black tree when you also need order — range queries, sorted iteration, predecessor and successor, minimum and maximum. Second, in main memory B-trees are steadily displacing red-black trees. A red-black node holds one key and is reached by following a pointer, so nearly every step down the tree is a cache miss, while a B-tree node packs dozens of keys into a couple of cache lines. Rust's standard BTreeMap is a B-tree for exactly this reason, and recent Linux versions have replaced some long-standing red-black trees with B-tree-like structures. The asymptotics are identical; the constants are not.