Java Reference
In-Depth Information
27.38
Splitting a 4-node whose parent is red: Cases 3 and 4.
Now consider the case in which the
4-node is the middle child of its 3-node parent. This time, we look at both red-black representa-
tions that the 3-node parent produces. Figure 27-37a shows one possible red-black tree. After the
color flip in Part
b
, we resolve the consecutive red nodes as we did in Figure 27-31d. A right-left
double rotation followed by a color flip produces the desired results, as you can see in the rest of
Figure 27-37.
Figure 27-38a shows the second possible red-black tree. After the color flip in Part
b
, we
resolve the consecutive red nodes as we did in Figure 27-32d. A left-right double rotation followed
by a color flip is necessary, as the rest of Figure 27-38 shows. Notice that the tree in Figure 27-38e
is the same as the one in Figure 27-37e.
FIGURE 27-37
Splitting a 4-node that has a red parent within a red-black
tree: Case 3
(a)
(b)
(c)
(d)
(e)
g
g
g
m
m
Color flip
Rotate left
p
p
m
g
p
g
p
Rotate right
m
p
s
s
m
l
l
s
Color flip
s
l
s
l
l
FIGURE 27-38
Splitting a 4-node that has a red parent within a red-black
tree: Case 4
(a)
(b)
(c)
(d)
(e)
p
p
p
m
m
Color flip
Rotate right
g
g
g
p
g
p
m
Rotate left
m
m
g
s
l
l
s
l
Color flip
s
s
l
s
l
Note:
Splitting a red-black 4-node
When splitting a red-black 4-node, the color of its parent determines the necessary opera-
tions. If the parent is black, a color flip is sufficient. But if the parent is red, a color flip, a
rotation, and another color flip are necessary.
