Red-black tree

A red-black tree is a type of balanced binary 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.

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.

See also: AVL tree, B-tree

External links

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