Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Insert the value exactly as in a plain search tree, and colour the new node red.
- Red is provisional: it adds no black nodes to any path, so only one rule can break.
- If the parent is also red, look at the uncle.
- Red uncle: recolour parent and uncle black, grandparent red, and check again one level up.
- Black uncle: rotate so the three nodes line up, then swap two colours.
- Finally force the root black — always legal, and it never breaks anything.
Key concepts
- Colour is data, not decoration — it encodes the balance budget
- Equal black-height on every path is what bounds the depth
- At most two rotations per insertion
- Depth stays within 2·log₂(n+1), whatever the input order
When to use it
When ordered data arrives in an order you do not control and worst-case lookup time matters. It is the structure behind Java's TreeMap and C++'s std::map.
Did you know
Rudolf Bayer invented them in 1972 as "symmetric binary B-trees". The red-and-black naming came later, reportedly because those were the two pen colours available.