Other algorithms / interactive lesson
Insert values into a Red-Black tree and watch BST placement, red-red violations, recoloring, rotations, NIL leaves, and invariant restoration step by step.
About the algorithm
A Red-Black tree is a self-balancing binary-search tree. It stores ordinary BST keys, but each node is colored red or black. The color rules constrain the shape of the tree enough to guarantee logarithmic search, insert, and delete time.
Red-Black trees were introduced by Rudolf Bayer in 1972 as symmetric binary B-trees and later named and popularized by Leonidas Guibas and Robert Sedgewick in 1978. They became widely used in language runtimes and standard libraries because they provide reliable logarithmic operations with relatively few rotations.
Insertion begins exactly like a normal binary-search tree insertion. The new node is colored red. If its parent is black, the tree is already valid. If parent and child are both red, the algorithm inspects the uncle. With a red uncle, it recolors parent and uncle black and grandparent red, then continues upward. With a black or missing uncle, it uses one or two rotations plus recoloring to remove the red-red violation locally. At the end, the root is forced black.
Red-Black trees are used for ordered maps and sets, indexes, schedulers, and memory-management structures. Examples include Java TreeMap and TreeSet, C++ std::map and std::set implementations, and many kernel or runtime data structures where predictable O(log n) performance matters.
Code companion
Connect each visual decision to an implementation pattern.
insert value as in a normal BST
color the new node red
while parent is red:
grandparent = parent.parent
uncle = sibling of parent
if uncle is red:
parent.color = black
uncle.color = black
grandparent.color = red
current = grandparent
else:
if current is an inner child:
rotate parent toward current
current = parent
recolor parent black
recolor grandparent red
rotate grandparent away from current
root.color = black