Java Reference
In-Depth Information
A color flip is all that is necessary when a red-black 4-node has a black parent. As you can see
from Figure 27-33, a black parent corresponds to a 2-node in the 2-4 tree. If a 4-node in a 2-4 tree
has a 3-node as its parent, the red-black 4-node will have a red parent. We examine this situation in
the next segment.
FIGURE 27-33
Splitting a 4-node whose parent is a 2-node in (a) a 2-4 tree;
(b) a red-black tree
(a)
p
p m
p
m p
OR
Split
Split
p m
p m
s m l
s
s m l
s
l
l
(b)
p
p
p
p
OR
m
m
m
m
s
s
s
l
s
l
l
l
27.36
Splitting a 4-node whose parent is red: Case 1.
Figure 27-34a shows the splitting of a 4-node that
has a 3-node parent within a 2-4 tree. Here, the 4-node is the right child of its parent. Figure 27-34b
shows the red-black representations of the two trees in Part
a
. How can we transform the first red-
black tree into the second? Figure 27-35 shows the necessary steps. In Part
a
, we detect a 4-node at
m
, since this black node has two red children. A color flip results in two adjacent red nodes, as
shown in Figure 27-35b. Earlier, in Figure 27-31c, we saw this configuration of a black node and
two consecutive right descendants that are red. As we did then, we perform a left rotation about
p
,
as Figure 27-35c shows, and then we reverse the colors of the nodes containing
p
and
g
. This color
flip, together with the rotation, resolves the illegal red nodes. The result in Figure 27-35d is the
desired red-black tree that we saw in Figure 27-34b.
Since a 3-node has two different red-black representations, we can replace Figure 27-35a with
a different red-black tree. We leave it to you to show that the final result will be the same, but with
less work. (See Exercise 13.)
27.37
Splitting a 4-node whose parent is red: Case 2.
The 4-node in Figure 27-34a is a right child of its
parent. If it were a left child, the red-black representation would be as in Figure 27-36a. The rest of
this figure shows that both color flips and a right rotation are necessary to split the 4-node.
As before, we can replace Figure 27-36a with a different red-black tree and get the same final
result. Again we leave the details to you as an exercise. (See Exercise 14.)
