Java Reference
In-Depth Information
FIGURE 27-28
Using 2-nodes to represent (a) a 4-node; (b) a 3-node
(a)
m
Split
s m l
s
l
T 1
T 2
T 3
T 4
T 1
T 2
T 3
T 4
(b)
s
l
Split
OR
s l
s
l
T 1
T 3
T 1
T 2
T 1
T 2
T 3
T 2
T 3
FIGURE 27-29
A red-black tree that is equivalent to the 2-4 tree in
Figure 27-27c
\
50
20
80
10
40
60
90
35
55
70
Properties of a Red-Black Tree
27.33
The root of every red-black tree is black. If the original 2-4 tree had a 2-node as its root, the 2-node
would be black. And if its root was either a 3-node or a 4-node, we would replace it with a subtree
whose root is black, as shown in Figure 27-28.
Since we create red nodes only when we convert 3-nodes and 4-nodes to 2-nodes, every red
node has a black parent, as you can see in Figure 27-29. It follows that a red node cannot have red
children. If it did, a red child would have a red parent, and this contradicts our previous conclusion
that every red node has a black parent.
When we formed a red-black tree equivalent to a 2-4 tree, 2-nodes stayed black and the repre-
sentation of any other node contained one black node. Thus, every node in a 2-4 tree produced
exactly one black node in the equivalent red-black tree. Since a 2-4 tree is completely balanced, all
paths from its root to a leaf connect the same number of nodes. So every path from the root to a leaf
in a red-black tree must contain the same number of black nodes.
 
Search WWH ::




Custom Search