Java Reference
In-Depth Information
FIGURE 27-32
The possible results of adding a new entry
e
to a two-node
red-black tree: mirror images of Figure 27-31
Red-black tree
Equivalent 2-4 tree
(a) Before addition
x
y x
y
Action after addition
to transform
column 1 into column 3
After adding
e
to
the red-black tree
After adding
e
to
the 2-4 tree
Red-black equivalent
of the 2-4 tree
None
(b) Case 1:
The tree is balanced
x
y x e
x
y
y
e
e
(c) Case 2:
A red node has a
red left child
Single right rotation
and color flip
x
e y x
y
y
e
x
e
(d) Case 3:
A red node has a
red right child
Left-right double
rotation and color flip
x
y e x
e
y
y
x
e
27.35
Splitting a 4-node whose parent is black.
During an addition to a 2-4 tree, we split any 4-nodes
that we encounter as we move along the path from the root to the eventual insertion point. We must
perform an equivalent action during an addition to a red-black tree. Figure 27-28a shows that when
a black node has two red children, we have encountered the red-black representation of a 4-node.
We will call this configuration a red-black 4-node, or simply a 4-node.
Note:
A red-black 4-node
A red-black 4-node consists of a black node and two red children.
Figure 27-33a recalls how to split a 4-node when its parent in the 2-4 tree is a 2-node. The mid-
dle entry
m
moves up to the node's parent, and the other entries
s
and
l
are given their own nodes as
replacement children of the parent. Figure 27-33b shows the corresponding red-black trees. Notice
that the three nodes in the subtree rooted at
m
reverse colors. Thus, we split the red-black represen-
tation of a 4-node by performing a color flip.
