Java Reference
In-Depth Information
8.
What tree results when you add the values 10, 20, 30, 40, 50, 60, 70, 80, 90, and 100 to each of the following
initially empty trees?
a. An AVL tree
b. A 2-3 tree
c. A 2-4 tree
d. A red-black tree
9.
Add the values given in Exercise 8 to an initially empty binary search tree. Compare the resulting tree with the
trees you created in Exercise 8. Which tree could you search most efficiently?
10.
Draw the shortest possible tree that contains 20 values for each of the following kinds of trees:
a. An AVL tree
b. A 2-3 tree
c. A 2-4 tree
d. A red-black tree
11.
Draw the tallest possible tree that contains 20 values for each of the following kinds of trees:
a. An AVL tree
b. A 2-3 tree
c. A 2-4 tree
d. A red-black tree
12.
Using pseudocode, describe an inorder traversal of
a. A 2-3 tree
b. A 2-4 tree
13.
Figure 27-34a shows a 4-node within a 2-4 tree that is the right child of a 3-node parent containing data items g
and p . When converting these nodes to red-black notation, make p be the parent of g . Revise Figure 27-35 to show
that a color flip is all that is necessary to get the desired red-black tree.
14.
Repeat Exercise 13, but this time assume that the 4-node is a left child.
15.
Color the nodes in each tree in Figure 27-39 so that it is a red-black tree.
FIGURE 27-39
Three binary trees for Exercise 15
(a)
(c)
(b)
16.
Which of the trees that you studied in this chapter could be used to implement a priority queue? Recall that we
discussed the priority queue in Chapter 10.
17.
How efficiently could a red-black tree or an AVL tree implement the add and remove methods of a priority queue?
18.
Consider a B-tree of order 1000 whose height is 3. What is the smallest number of values that this tree can
contain? What is the largest number of values? Generalize your results to a B-tree of order 1000 and height h .
P ROJECTS
1.
You remove an entry from an AVL tree in the same way that you remove an entry from a binary search tree.
However, after you remove the appropriate node from the tree, an imbalance can occur that you must correct by
performing single or double rotations. Develop an algorithm that removes a node from an AVL tree.
2.
Implement a class of AVL trees.
 
Search WWH ::




Custom Search