Java Reference
In-Depth Information
The entry 70 belongs in the root's middle subtree, and since this leaf can accept another entry,
we add 70 there. Figure 27-14c shows the tree after this addition.
FIGURE 27-14
The 2-3 tree after adding (a) 80; (b) 90; (c) 70
(c)
(a)
(b)
50
50
50 80
50 80
Split
20
20
60
80
20
60 80
90
20
60
90
60
70
90
27.18
Adding 55.
When we add 55 to the tree in Figure 27-14c, the search algorithm terminates at the
root's middle subtree—a leaf—as Figure 27-15a indicates. Since this leaf cannot accommodate
another entry, we split the leaf and move 60 up a level to the root, as shown in Figure 27-15b.
Moving the 60 causes the root to split, and 60 moves up another level to a new node that becomes
the new root. Figure 27-15c shows the result of this addition.
FIGURE 27-15
Adding 55 to the 2-3 tree causes a leaf and then the root to split
(a)
(c)
(b)
60
50
80
50 80
50 60 80
20
55
60 70
90
20
55
70
90
20
55
70
90
27.19
Adding 10, 40, and 35.
The leaf that contains 20 has room for 10 as an additional entry, as
Figure 27-16a shows. An additional entry, 40, belongs in the same leaf. Since the leaf already con-
tains two entries, we split it and move 20 up a level to the node that contains 50. Figures 27-16b and
27-16c show this result. Finally, Figure 27-17 shows the result of adding 35 to the tree. The leaf
that contains 40 accommodates this new entry.
FIGURE 27-16
The 2-3 tree after adding (a) 10; (b), (c) 40
(a)
(b)
(c)
60
60
60
50
80
50
80
20 50
80
10
20
55
70
90
10 20
40
55
70
90
10
90
40
55
70
