Red-black tree

Colour-balanced. New nodes go in red; when that puts two reds in a row, a recolour or a rotation restores the rules.

Build the tree

Show NIL leaves — the black sentinels every path ends at

Value

Several at once

Course examples

Each one clears the tree first and inserts from scratch.

Nine values in a helpful order — the tree stays short.

The same nine values in order. The tree becomes a stick, and searching it is no better than scanning a list — this is why the balanced trees exist.

The red-black page's worked example. In a red-black tree it exercises a zig-zag rotation (40), a recolour (20), and a zig-zig rotation (10).

Nodes: 0 of 24

Height: —

The tree is empty — insert a value, or load a course example, to begin.

Insert a value, or load one of the course examples.

step 0 / 0