Red-Black Tree — Self-Balancing BST

🌲 Red-Black Tree

Self-balancing BST

Insert a key to begin

Last fix: —

Insert / delete a key

Stats

Nodes

Black-height

Tree height

log₂(n)

Rotations

Recolours

Info & Theory

A red-black tree is a binary search tree where each node carries one extra colour bit. Five rules keep it balanced so that search, insert and delete are all O(log n).

The five properties

Every node is red or black.
The root is black.
Every leaf (NIL) is black.
A red node has no red child.
Every path from a node to its leaves has the same number of black nodes — the black-height.

Insertion fix-up

A new key is added as a red leaf. If its parent is also red we have a violation. If the uncle is red, we recolour parent, uncle and grandparent and continue up. If the uncle is black, we rotate (left and/or right) and recolour to fix it locally.

Rotations

A left rotation lifts a node's right child above it; a right rotation lifts its left child. Each is an O(1) pointer shuffle that keeps the in-order key order intact while changing the shape.

Height bound

A tree with n keys has height at most 2·log₂(n+1). Watch the height stat track log₂(n) as you insert.

How this simulation works

This is a real red-black tree, not a recorded animation. Every key you type is inserted with the genuine binary-search-tree rule, coloured red, and then repaired by the standard insert-fixup loop: it inspects the colour of the new node's uncle and either recolours the parent, uncle and grandparent, or performs one or two rotations followed by a recolour. The root is always forced black at the end. Deletion uses the matching delete-fixup, resolving a temporary "double-black" with recolouring and rotations.

Reading the canvas

Nodes are drawn red or black to match their colour bit, edges connect parents to children, and each node is labelled with its key. The stats panel reports the live node count, the black-height (constant on every path by definition), the actual tree height next to log₂(n), and how many rotations and recolours the last operation needed. Use Random to fire in keys quickly and watch the structure rebalance.

Frequently asked questions

What is a red-black tree?

A red-black tree is a self-balancing binary search tree. Each node carries one extra bit of colour, red or black, and a set of colour rules keeps the longest root-to-leaf path no more than twice the shortest, guaranteeing O(log n) search, insert and delete.

What are the red-black tree properties?

Every node is red or black; the root is black; every leaf (the NIL sentinel) is black; a red node never has a red child; and every path from a node down to its descendant leaves contains the same number of black nodes (the black-height).

What is the black-height?

The black-height of a node is the number of black nodes on any path from that node down to a leaf, not counting the node itself. Because every such path has the same count, the tree stays roughly balanced.

How does insertion keep the tree balanced?

A new key is inserted as a red leaf using the normal binary-search-tree rule, then a fix-up loop repairs any red-red violation. Depending on the colour of the uncle node it either recolours the parent, uncle and grandparent, or performs one or two rotations and recolours, then continues up to the root, which is finally forced black.

What is a rotation?

A rotation is a local restructuring that changes a few parent-child links to lower one subtree and raise another while preserving the in-order key sequence. A left rotation lifts a node's right child above it; a right rotation lifts the left child. Rotations run in O(1) time.

Why use recolouring instead of always rotating?

When the uncle of the new node is also red, simply flipping the colours of parent, uncle and grandparent fixes the local red-red conflict without moving any pointers, then pushes the possible new conflict two levels up. Rotations are only needed when the uncle is black.

How tall can a red-black tree get?

A red-black tree with n keys has height at most 2·log2(n+1). The simulation shows the actual height beside log2(n) so you can see the real height tracking the logarithm as keys are added.

How is a red-black tree different from an AVL tree?

Both are self-balancing BSTs with O(log n) operations. AVL trees keep a stricter height balance, so they are slightly faster for lookups but do more rotations on insert and delete. Red-black trees rebalance more loosely with fewer rotations, which is why they back many standard-library maps and the Linux kernel.

Where are red-black trees used in practice?

They underpin ordered associative containers such as C++ std::map and std::set, Java TreeMap and TreeSet, and the Completely Fair Scheduler and many other structures inside the Linux kernel.

What happens on deletion?

Deletion removes the key with the standard BST procedure, then if a black node was removed it runs a fix-up that pushes an extra "double-black" weight up the tree, resolving it with recolouring and rotations until the equal-black-height property is restored.

About Red-Black Tree

Last updated: 5 July 2026

A red-black tree is a self-balancing binary search tree introduced by Rudolf Bayer (1972) and later named by Leonidas Guibas and Robert Sedgewick (1978). It maintains four colour invariants: the root is black; no red node has a red parent; every path from any node to a null leaf contains the same number of black nodes (the black-height); and null leaves are treated as black. These rules ensure the tree's height never exceeds 2·log₂(n+1), guaranteeing O(log n) worst-case time for search, insertion, and deletion. Red-black trees back the standard map/set containers in C++ (std::map), Java (TreeMap), and Linux's completely fair scheduler (CFS).

This simulation lets you insert or delete keys one at a time, watching each recolouring step and left/right rotation animate in real time. A height counter compares the current red-black tree height against an equivalent unbalanced BST to show the practical benefit of the invariants.

Frequently Asked Questions

What are the four red-black tree invariants?

1) Every node is either red or black. 2) The root is black. 3) Every null (leaf) is black. 4) If a node is red, both its children are black (no two consecutive red nodes on any path). Additionally, 5) all paths from any node to its descendant null leaves pass through the same number of black nodes — this is the black-height property that ensures balance.

How many rotations can a single insertion require?

At most two rotations per insertion, plus O(log n) recolouring operations that propagate upward. In contrast, an AVL tree may require O(log n) rotations after an insertion (though in practice it averages fewer). For deletion, a red-black tree may need at most three rotations. This bounded rotation count makes red-black trees attractive in systems where rotations are expensive, such as persistent or functional data structures.

How does a red-black tree compare to an AVL tree?

AVL trees maintain a stricter height balance (height difference between subtrees ≤ 1), resulting in slightly faster lookups on average. Red-black trees allow a height ratio of up to 2:1 between the longest and shortest paths, which permits faster insertions and deletions due to fewer rotations. In write-heavy workloads (databases, OS schedulers) red-black trees are typically preferred; in read-heavy lookup tables AVL trees may be faster.

What is a left rotation and when is it applied?

A left rotation around node x makes x's right child y become the new subtree root, moving x down to y's left child and adopting y's former left subtree as x's new right child. It is applied when the tree has a right-leaning imbalance — specifically during insertion when the new red node is a right child of a right child (the "right-right" case in insertion fix-up).

Why does the black-height property guarantee O(log n) height?

Let bh(x) be the black-height of node x. By the no-consecutive-reds rule, at most half the nodes on any root-to-leaf path can be red, so the actual height h ≤ 2·bh(root). The subtree rooted at any node with black-height k contains at least 2^k−1 internal nodes, so n ≥ 2^bh−1, giving bh ≤ log₂(n+1) and h ≤ 2·log₂(n+1).

How are red-black trees used in the Linux kernel?

Linux's Completely Fair Scheduler (CFS) stores runnable processes in a red-black tree keyed by virtual runtime, so the process with the smallest runtime (the next to run) can be found in O(log n) time. The kernel's memory manager uses red-black trees to track virtual memory areas (VMAs) per process, and the epoll subsystem uses them to manage file descriptors efficiently.

What is a 2-3-4 tree and how does it relate to a red-black tree?

A 2-3-4 tree (or B-tree of order 4) stores 1–3 keys per node with 2–4 children, maintaining perfect balance. Every 2-3-4 tree maps exactly to a red-black tree: a 2-node becomes a single black node; a 3-node becomes a black node with a red child; a 4-node becomes a black node with two red children. This correspondence gives an alternative proof of red-black tree correctness and underpins the LLRB (left-leaning red-black) tree variant.

What is a Left-Leaning Red-Black (LLRB) tree?

The LLRB variant, popularised by Robert Sedgewick (2008), adds the constraint that red links always lean left (a red node is always a left child). This reduces the number of structural cases to handle during insertion and deletion from about 6–8 to 3, resulting in implementations of roughly 50 lines of code versus 200+ for the standard Cormen-Leiserson-Rivest formulation. Java's TreeMap uses the standard formulation; some functional language libraries prefer LLRB.

Can red-black trees be made persistent?

Yes. Because each insertion or deletion modifies only O(log n) nodes (along the path from root to the affected leaf), a persistent red-black tree can be created by path-copying: duplicating only the O(log n) nodes that change and sharing the rest. This gives O(log n) time and space per operation with full version history, and is used in persistent functional data structures such as Clojure's sorted maps.

How does deletion in a red-black tree work?

Deletion first performs a standard BST deletion (replacing the node with its in-order successor if it has two children). If the deleted node or its replacement was red, no black-height violation occurs. If a black node is removed, a "double-black" deficit propagates upward and is resolved by six cases of sibling-colour and nephew-colour analysis, each either re-rooting a subtree with rotations and recolouring, or pushing the deficit up. At most three rotations suffice.