## Description

1. AVL tree

(a) Suppose that we insert a sequence of keys 2, 1, 3, 7, 9 into an initially empty AVL

tree. Draw the resulting AVL tree.

(b) Suppose that we further insert key 6 into the AVL tree you get in Problem (1a).

Draw the resulting AVL tree.

(c) Suppose that we further insert keys 4, 5 into the AVL tree you get in Problem (1b).

Draw the resulting AVL tree.

(d) Suppose that we further insert keys 8, 10, 11, into the AVL tree you get in

Problem (1c). Draw the resulting AVL tree.

(e) Write down the balance factor for each node in the final AVL tree you get in

Problem (1d).

2. Red-black tree

(a) Suppose that we insert a sequence of keys 9, 3, 1 into an initially empty red-black

tree. Draw the resulting red-black tree.

(b) Suppose that we further insert key 6 into the red-black tree you get in Problem (2a). Draw the resulting red-black tree.

(c) Suppose that we further insert keys 2, 8 into the red-black tree you get in Problem (2b). Draw the resulting red-black tree.

(d) Suppose that we further insert key 7 into the red-black tree you get in Problem (2c). Draw the resulting red-black tree.

(e) Suppose that we further insert keys 4, 5 into the red-black tree you get in Problem (2d). Draw the resulting red-black tree.

When you draw the red-black tree, please indicate the color of each node in the tree.

For example, you can color each node or put a letter b/r near each node.

1

3. Show that any arbitrary n-node binary search tree can be transformed into any other

arbitrary n-node binary search tree using O(n) rotations. (Hint: First show that at

most n−1 right rotations suffice to transform the tree into a right-skewed binary search

tree.)

4. Suppose that an AVL tree insertion breaks the AVL balance condition. Suppose node

P is the first node that has a balance condition violation in the insertion access path

from the leaf. Assume the key is inserted into the left subtree of P and the left child

of P is node A. Prove the following claims:

(a) Before insertion, the balance factor of node P is 1. After insertion and before

applying rotation to fix the violation, the balance factor of node P is 2.

(b) Before insertion, the balance factor of node A is 0. After insertion and before

applying rotation to fix the violation, the balance factor of node A cannot be 0.

2