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 have 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 rotating nodes.
See Also: B tree