Java Reference
In-Depth Information
27.26
Adding 80 and 90.
To add an entry to the 2-4 tree in Figure 27-22c, we find that the root is a
4-node. We split it by moving the middle entry, 50, up. Since we are at a root, we create a new node
for the 50. That node becomes the new root of the tree, as shown in Figure 27-23a. We now can add
80 and 90 to the root's right leaf, as Figures 27-23b and 27-23c illustrate.
FIGURE 27-23
The 2-4 tree after (a) splitting the root; (b) adding 80; (c) adding 90
(a)
(b)
(c)
50
50
50
20
60
20
60
80
20
60 80
90
27.27
Adding 70.
While searching the 2-4 tree in Figure 27-23c for a place to add 70, we encounter the
4-node that is the root's right child. We split this node into two nodes and move the middle entry 80
up to the root. The result of this split is shown in Figure 27-24a. We now have room to add 70 to the
root's middle child, as Figure 27-24b shows.
FIGURE 27-24
The 2-4 tree after (a) splitting a 4-node; (b) adding 70
(a)
(b)
50 80
50 80
20
60
20
60
70
90
90
27.28
Adding 55, 10, and 40.
The 2-4 tree in Figure 27-24b can accommodate the addition of 55, 10, and
40 without splitting nodes. Figure 27-25 shows the results of these additions.
FIGURE 27-25
The 2-4 tree after adding (a) 55; (b) 10; (c) 40
(b)
(c)
(a)
50 80
50 80
50 80
20
55
60 70
10
20
55 60 70
90
90
10 20
40
55 60 70
90
27.29
Adding 35.
While adding 35 to the 2-4 tree in Figure 27-25c, our search encounters the root's left
child, which is a 4-node. We split this node into two nodes and move the middle entry, 20, up to the
root, as shown in Figure 27-26a. We now can add 35 to the root's middle left child, as Figure 27-26b
shows. This is the final addition that we will make.
