06-10-2012, 11:30 AM
Red-Black Trees
RedBlack.pdf (Size: 43.35 KB / Downloads: 142)
Definition.
A red-black tree is a extended binary tree in which
each node has a color — either red or black. These conditions
must hold:
1) [red-red condition] A child and its parent cannot both be
red.
2) [black-balance condition] Every path from the root to an
external node contains the same number of black nodes.
The number of nodes on the path to an external node (not
counting the external node itself) is called the black height.
3) [black root condition] The root is black.
We may treat the external nodes as being black, or as not having
a color.
Conditions (1) and (2) ensure that the tree isn’t grossly
unbalanced.
(1) says that there cannot be too many red nodes.
(2) says that, if we disregard the limited number of red nodes,
the tree is perfectly balanced.
Condition (3) is trivial. If the root is red, simply recolor it black.
(This won’t destroy (1) or (2).)
Red-Black Trees — fix-up after insertion
Let T be a red-black tree.
After inserting a new node c into T, how do we restore the redblack
tree properties?
1) After inserting c, we color it red.
Exception: If T was empty, c becomes the root, and we
color it black. In this case, we have a one-node red-black
tree. We are done.
Coloring c red ensures that black balance still holds.
2) If the parent of c (call it p) is black, the red-red condition still
holds. No fixup is needed. We are done.
3) If p is red, we have a single red-red violation — at (p,c). This
is the only problem.
How do we fix up a tree that satisfies all the conditions for a redblack
tree, except for a single red-red violation. (A parent p and
child c are both red.)
4) If p is the root, simply re-color p black. The black height
increases by 1, but the black balance condition still holds.
We are done.