5.6.1 AVL Trees

1.

Draw all possible binary search trees containing the key values 1, 2, 3, 4. Which of these are AVL trees?

2.

In each of the following, insert the keys in the order shown, to build them into AVL trees.

(a)

A, Z, B, Y, C, X, D, W, E, V, F.

(b)

A, B, C, D, E, F, G, H, I, J, K, L.

(c)

A, V, L, T, R, E, I, S, O, K.

In each case, do the following:

(a)

Delete each of the the keys inserted in LIFO order (last key inserted is first deleted).

(b)

Delete each of the keys inserted in FIFO order (first key inserted is first deleted).

3.

An AVL tree is constructed by inserting the key values 1, 2, 3, 4, 5 in some order specified by a permutation of 1, 2, 3, 4, 5, into an initially empty tree. For which of these permutations is there no need to do any rotations at any stage during the insertions?

4.

Show that the number of (single or double) rotations done in deleting a key from an AVL tree cannot exceed half the height of the tree.