Java Reference
In-Depth Information
exercises
IN SHORT
19.1
Show the result of inserting 3, 1, 4, 6, 9, 2, 5, and 7 in an initially
empty binary search tree. Then show the result of deleting the root.
Draw all binary search trees that can result from inserting permuta-
tions of 1, 2, 3, and 4. How many trees are there? What are the prob-
abilities of each tree's occurring if all permutations are equally
likely?
19.2
Draw all AVL trees that can result from inserting permutations of 1, 2,
and 3. How many trees are there? What are the probabilities of each
tree's occurring if all permutations are equally likely?
19.3
Repeat Exercise 19.3 for four elements.
19.4
19.5
Show the result of inserting 2, 1, 4, 5, 9, 3, 6, and 7 into an initially
empty AVL tree. Then show the result for a top-down red-black
tree.
19.6
Repeat Exercises 19.3 and 19.4 for a red-black tree.
IN THEORY
19.7
Prove Theorem 19.2.
19.8
Show the result of inserting items 1 through 15 in order in an initially
empty AVL tree. Generalize this result (with proof) to show what hap-
pens when items 1 through 2 k - 1 are inserted into an initially empty
AVL tree.
19.9
Give an algorithm to perform remove in an AVL tree.
19.10
Prove that the height of a red-black tree is at most approximately
2 log N and give an insertion sequence that achieves this bound.
Show that every AVL tree can be colored as a red-black tree. Do all
red-black trees satisfy the AVL tree property?
19.11
Prove that the algorithm for deletion in an AA-tree is correct.
19.12
Suppose that the level data member in an AA-tree is represented by
an 8-bit byte . What is the smallest AA-tree that would overflow the
level data member at the root?
19.13
A B*-tree of order M is a B-tree in which each interior node has
between 2 M / 3 and M children. Leaves are similarly filled. Describe a
method that can be used to perform insertion in a B*-tree.
19.14
 
Search WWH ::




Custom Search