1. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.
2. Keys 1, 2, ... , 2k - 1 are inserted in order into an initially empty AVL tree. Prove that the resulting tree is perfectly balanced.
3. Write the remaining procedures to implement AVL single and double rotations.
4. Design a linear-time algorithm that veri?es that the height information in an AVL tree is correctly maintained and that the balance property is in order.
5. Write a nonrecursive function to insert into an AVL tree.
6. Show that the deletion algorithm in Figure 4.47 is correct