Red-black trees

In addition to the requirements imposed on a binary search tree the following must be satisfied by a red–black tree:[16]


  1. Each node is either red or black.
  2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
  3. All leaves (NIL) are black.
  4. If a node is red, then both its children are black.
  5. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.


The only constraint on the children of black nodes is (5). In particular, a black node (like a leaf node) may have a black parent; for example, every perfect binary tree that consists only of black nodes is a red-black tree.

The black depth of a node is defined as the number of black nodes from the root to that node (i.e. the number of black ancestors). The black height of a red–black tree is the number of black nodes in any path from the root to the leaves, which, by property 5, is constant (alternatively, it could be defined as the black depth of any leaf node).[17]

These constraints enforce a critical property of red–black trees: the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree is roughly height-balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red–black trees to be efficient in the worst case, unlike ordinary binary search trees.

To see why this is guaranteed, consider a red–black tree having a black height of b, i.e. the path from the root to any leaf has b black nodes. There can be at most one red node between each two black nodes (property 4), so there are at most b red nodes on the path. Thus the total path length must be between b+0 = b (no red nodes present) and b+b = 2b (alternating black and red).

Comments

Popular Posts