Java Reference
In-Depth Information
FIGURE 27-26
The 2-4 tree after (a) splitting the leftmost 4-node; (b) adding 35
(a)
(b)
20 50 80
20 50 80
10
55 60 70
10
35
40
55 60 70
90
40
90
Note:
When adding a new entry to a 2-4 tree, you split any 4-node as soon as you encoun-
ter it during the search for the new entry's position in the tree. The addition is complete right
after this search ends. Thus, adding to a 2-4 tree is more efficient than adding to a 2-3 tree.
Question 16
What comparisons are made while searching the 2-4 tree in Figure 27-26b
for each of the following values?
a.
5
b.
56
c.
41
d.
30
Question 17
What tree results when you add 30 to the 2-4 tree in Figure 27-26b?
Question 18
What 2-4 tree results when you make the following additions to an initially
empty 2-4 tree? 70, 80, 90, 20, 10, 50, 60, 40, 30
Question 19
How does the tree that you created in the previous question compare to the
2-3 tree you created in Question 14?
Figure 27-27 compares the AVL tree in Figure 27-10a, the final 2-3 tree in Figure 27-17, and the 2-4 tree
that we just constructed. The AVL tree is a balanced binary search tree of height 4. The other trees are
completely balanced general search trees. The height of the 2-3 tree is 3; the height of the 2-4 tree is 2. In
general, 2-4 trees are shorter than 2-3 trees, which are shorter than AVL trees.
FIGURE 27-27
Three balanced search trees obtained by adding 60, 50, 20, 80,
90, 70, 55, 10, 40, and 35: (a) AVL tree; (b) 2-3 tree; (c) 2-4 tree
(a)
(b)
(c)
60
60
20 50 80
40
10
35 40
55 60 70
90
80
20 50
80
90
35 40
20
50
70
10
55
70
90
10
35
55
