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.