Java Reference
In-Depth Information
occurs in the node's left subtree. Data that is greater than the largest data item
l
occurs in the node's
right subtree. Data that is between
s
and the middle data item
m
or between
m
and
l
occurs in the
node's middle subtrees. Figure 27-21 illustrates a typical 4-node.
Searching a 2-4 tree is like searching a 2-3 tree, but with additional logic to handle the 4-nodes.
This search forms the basis of an algorithm to add entries to a 2-4 tree.
VideoNote
2-4 and red-black trees
FIGURE 27-21
A 4-node
sm
l
s
s
m
l
m
l
Note:
A 2-4 tree is a general search tree whose interior nodes must have two, three, or four
children and whose leaves occur on the same level. A 2-4 tree is completely balanced.
Recall how we add a new entry to a 2-3 tree. We make comparisons along a path that begins at the
root and ends at a leaf. At this point, if the leaf is a 3-node, it already contains two data entries, and
so we must split it. Since an entry would now move up a level, this split could require splits in
nodes above the leaf. Thus, adding to a 2-3 tree can require us to retrace the path from the leaf back
to the root.
In a 2-4 tree, we avoid this retrace by splitting each 4-node as soon as we first consider it dur-
ing the search from root to leaf. After a split, the next node along the comparison path is the result
of the split, and so is not a 4-node. If this node has a 4-node child that we consider next, it has room
for the entry that moves up from this child. No other splits occur, as would happen in a 2-3 tree.
You will see an example of this shortly.
As in the previous section, we will use an example to demonstrate how to add entries to a
2-4 tree. So that we can compare our results with previous trees, we will use the same sequence
of additions—namely, 60, 50, 20, 80, 90, 70, 55, 10, 40, and 35—that we used earlier.
27.25
Adding 60, 50, and 20.
Figure 27-22 shows the effect of adding 60, 50, and 20 to an initially empty
2-4 tree. The resulting tree consists of a single 4-node.
FIGURE 27-22
An initially empty 2-4 tree after adding (a) 60; (b) 50; (c) 20
(a)
(b)
(c)
60
50
60
20
50 60
