Page 162 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

4. Show the keys with which each of the following targets will be compared in a search of the Notes
preceding binary search tree.
a. c b. s c. k
d. a e. d f. m
g. f h. b i. t

5. Insert each of the following keys into the preceding binary search tree. Show the comparisons
of keys that will be made in each case. Do each part independently, inserting the key into
the original tree.

a. m b. f c. b
d. t e. c f. s
6. Delete each of the following keys from the preceding binary search tree, using the algorithm
developed in this section. Do each part independently, deleting the key from the original
tree.
a. a b. p c. n
d. s e. e f. k

7. Draw the binary search trees that function insert will construct for the list of 14 names
presented in each of the following orders and inserted into a previously empty binary
search tree.
a. Jan Guy Jon Ann Jim Eva Amy Tim Ron Kim Tom Roy Kay Dot
b. Amy Tom Tim Ann Roy Dot Eva Ron Kim Kay Guy Jon Jan Jim
c. Jan Jon Tim Ron Guy Ann Jim Tom Amy Eva Roy Kim Dot Kay
d. Jon Roy Tom Eva Tim Kim Ann Ron Jan Amy Dot Guy Jim Kay
8. Consider building two binary search trees containing the integer keys 1 to 63, inclusive,
received in the orders
a. All the odd integers in order (1, 3, 5, : : : , 63), then 32, 16, 48, then the remaining even
integers in order (2, 4, 6, : : : ).
b. 32, 16, 48, then all the odd integers in order (1, 3, 5, : : : , 63), then the remaining even
integers in order (2, 4, 6, : : : ).
Which of these trees will be quicker to build? Explain why. [Try to answer this question
without actually drawing the trees.]
9. Prepare a package containing the declarations for a binary search tree and the functions
developed in this section. The package should be suitable for inclusion in any application
program.
10. In each of the following, insert the keys, in the order shown, to build them into an AVL
tree.
a. A, Z, B, Y, C, X.
b. A, B, C, D, E, F.

c. M, T, E, A, Z, G, P.
d. A, Z, B, Y, C, X, D, W, E, V, F.
e. A, B, C, D, E, F, G, H, I, J, K, L.
f. A, V, L, T, R, E, I, S, O, K.

LOVELY PROFESSIONAL UNIVERSITY 157