A binary search tree is fast only while it stays bushy. Insert keys in sorted order and it degrades into a linked list, and every operation becomes O(n). A red-black tree is a binary search tree that paints each node red or black and keeps a few rules about those colors. The rules guarantee the tree's height stays below 2·log₂(n + 1), so search, insert and delete are all O(log n).
Why does that keep the tree balanced? Take the shortest path from the root down: at best it is all black. The longest path can only add red nodes in between those black ones, and never two in a row (rule 4). So no path is more than twice as long as any other.
First insert it like any binary search tree: walk down from the root, going left when smaller and right when larger, and attach it at the empty spot you reach. Color it red. A red node doesn't change any black-height, so rule 5 is safe. The only rule that can break is rule 4, if its parent is also red.
To repair it we look at the new node's family. These names are used everywhere on this page:
| Situation | What to do |
|---|---|
| N is the root | Color it black. Done. |
| P is black | Nothing is broken. Done. |
| P is red, U is red | Recolor: P and U black, G red. G may now clash with its parent, so repeat with G as the new N. |
| P red, U black, triangle N is an inner child: N and P lean opposite ways (a zig-zag). | Rotate at P to straighten the zig-zag into a line. This becomes the line case, with the old P as N. |
| P red, U black, line N is an outer child: N and P lean the same way. | Rotate at G so P moves up, then swap the colors of P and G. Done. |
Recoloring may climb up the tree several times. Rotations happen at most twice per insertion, and after a rotation the fix-up is finished.
A rotation lifts a child into its parent's place while keeping the left-to-right order of keys unchanged. A left rotation lifts the right child; a right rotation lifts the left child. The lifted node's inner subtree (highlighted) switches parents.