Java Reference
In-Depth Information
FIGURE 27-34
Splitting a 4-node that has a 3-node parent within (a) a 2-4 tree;
(b) a red-black tree
(a)
g p m
g p
Split
p m
s
s m l
l
(b)
g
p
g
p
m
s
m
l
s
l
FIGURE 27-35
Splitting a 4-node that has a red parent within a red-black
tree: Case 1
(d)
(a)
(b)
(c)
g
g
p
p
Color flip
Rotate left
g
p
p
m
g
m
s
m
m
s
l
l
Color flip
s
s
l
l
FIGURE 27-36
Splitting a 4-node that has a red parent within a red-black
tree: Case 2
(a)
(b)
(c)
(d)
p
g
p
g
Color flip
Rotate right
g
g
p
m
m
p
m
m
s
s
l
l
Color flip
s
s
l
l
Search WWH ::




Custom Search