Red-black tree

A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science. It was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-trees".

A red-black tree is a binary tree where each node has color as an extra attribute, either red or black. By constraining the coloring of the nodes it is ensured that the longest path from the root to a leaf is no longer than twice the length of the shortest path. This means that the tree is balanced. A red-black tree must satisfy these properties:

The root is black
All leaves are black.
Red nodes can only have black children.
All paths from a node to its leaves contain the same number of black nodes.

A common source of confusion with these properties is that they assume that all the leaves in the tree are nil leaves, which contain no data and serve merely to indicate where the tree ends. These nodes are often omitted in drawings, resulting in a tree which seems to contradict the above principles, but which in fact does not.

An example of a red-black tree

When nodes are removed or deleted, the tree must be transformed to keep these properties. This is done by repainting or rotating nodes.

A newly added node should be red by default. If the parent node is black, the tree is still valid. If both the parent node is red, and there exists a red uncle node, then they should be repainted black, and the grandparent node should be repainted red. (It may be necessary to continue repainting up to the root.) Otherwise, rotations are necessary. If the root ends up red, it should be repainted black.

External links

An example (animated GIF, 200KB)
An example (static picture)