Transcript Red-black trees

Red-black trees
1. Red-black trees: a binary tree representation of 2-3-4
trees.
•
Definition: Red-black trees are binary search trees with
each node colored red or black and satisfying the
following properties:
i.
Root property: The root is black.
ii. External property: All external nodes are black.
iii. Internal property: The children of red nodes are black.
iv. Depth property: All external nodes have the same black
depth. The black depth is the number of black ancestors
minus one, or the number of black links from the root to
the node.
Red-black trees
• Red-black trees are an important data
structure but their combinatorial properties
are not much studied. They were introduced
by R. Bayer ("Symmetric binary B-trees:
Data structures and maintenance
algorithms", Acta Informatica, 1 (1972)
290-306).
Cont…
• From a combinatorial point of view, a red-black
tree is an extended binary tree (every node has two
children or is a leaf) which satisfies the following
properties.
• Every node is colored either red or black.
• Every leaf node is colored black.
• If a node is red, then both of its children are black.
• Every path from the root to a leaf contains the
same number of black nodes. This number is
called the black-height of the tree.
Example