** Next:** 5.6.2 Red-Black Trees
** Up:** 5.6 Problems
** Previous:** 5.6 Problems

- 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.

** Next:** 5.6.2 Red-Black Trees
** Up:** 5.6 Problems
** Previous:** 5.6 Problems
eEL,CSA_Dept,IISc,Bangalore