mastorna.it
IT

Algorithms · Balanced data structures

Red-black trees

A red-black tree is a binary search tree that limits imbalance through colors, recoloring and rotations. It is not perfectly balanced, but it guarantees logarithmic height.

From a plain BST to a worst-case guarantee

A BST built from sorted keys can degenerate into a chain of height n. A red-black tree preserves the BST property and constrains colors along paths: no path can become more than twice as long as another.

Order

Keys remain organized like any BST; in-order traversal is increasing.

Color

Every node adds one logical bit: red or black.

Local repair

After an update, recoloring and a constant number of rotations are enough.

The five red-black invariants

  1. 1

    Every node is either red or black.

  2. 2

    The root is black.

  3. 3

    Every NIL leaf—that is, every null pointer—is black.

  4. 4

    A red node has black parent and children: two red nodes can never be consecutive.

  5. 5

    Every path from a node to a descendant NIL contains the same number of black nodes: its black height.

NIL convention. Null pointers are hidden in the drawing, but the checker counts them as black leaves. This convention makes invariants and algorithms uniform.

Lab: watch the fix-up

Every new key enters red. Step through the trace to see which violation appears and how recoloring and rotations move or remove it.

Guided cases

Nodes
0
Height
0
Black-height
0
Rotations
0
Recolorings
0
  1. BST-insert(z); z.color ← RED
  2. while color(parent(z)) = RED
  3. if color(uncle(z)) = RED: recolor and move z up
  4. else if z is an inner child: rotate parent(z)
  5. recolor parent and grandparent
  6. rotate grandparent(z)
  7. root.color ← BLACK
red node black node current node z changed this step

Insert like a BST, then repair

  1. Find a NIL leaf through ordinary BST search and attach the new node.
  2. Color it red so every path keeps the same black height.
  3. If its parent is black, every invariant already holds.
  4. If its parent is red, inspect the uncle and geometry, then apply fix-up.
  5. Finally, force the root to black.
Why is the new node red? Making it black would immediately increase one path’s black height. Making it red can only violate the red–red rule, which can be repaired locally.

The core fix-up cases

Case 1

Red uncle: recolor

Parent and uncle become black, grandparent becomes red and z moves to the grandparent. The violation may propagate upward.

Case 2

Triangle: straighten

z is an inner child. Rotate its parent to turn the triangle into a line, reducing to the next case.

Case 3

Line: recolor and rotate

The parent becomes black, the grandparent red, and a rotation at the grandparent removes the red–red pair.

Right–left cases mirror left–right cases. The visualizer explicitly names the chosen direction.

Why height stays logarithmic

Contract each red node into its black parent. The red–red rule lets each black node absorb at most two red children; black height makes every resulting path equally long. Therefore:

h ≤ 2 log₂(n + 1)

OperationWorst-case timeNote
SearchΘ(log n)Follows one path.
InsertionΘ(log n)Search + fix-up; at most 2 rotations.
DeletionΘ(log n)Search + fix-up; at most 3 rotations.
Space per nodeΘ(1)Color and pointers.

Why deletion is more delicate

Deleting a red node does not change black height. Deleting a black node removes one black from paths through it, so the algorithm temporarily represents the deficit as “double black” and repairs it by inspecting sibling and nephews. There are more cases, but the tools are the same: recoloring and rotations.

The lab focuses on insertion because it makes every essential principle readable without compressing the many symmetric deletion cases into one view.

Common mistakes

  • Ignoring NIL pointers in the analysis: they are black leaves and count toward black height.
  • Assuming red-black means perfectly balanced: the guarantee is h ≤ 2 log₂(n+1), not complete levels.
  • Forgetting the mirror cases when the parent is the grandparent’s right child.
  • Rotating without updating root and parents, or recoloring before correctly identifying uncle and grandparent.
  • Counting every node instead of only black nodes when checking black height.