1. (5 points) Weiss Problem 4.4 ("Show" means "Prove by induction").
2. (15 points) Weiss Problem 4.9. In part (a) show the tree after each insertion. After performing the deletion as asked in part (b) what is the height of the resulting tree? What is its depth? Is it an AVL tree? Could it have been obtained as a result of splay tree operations? Is it a B-tree of any order?
3. (10 points) Weiss Problem 4.19. Show the tree after each insertion.
4 (10 points) Given a binary search tree, write a function (in pseudo-code) that returns true if the BST is an AVL tree and false otherwise (Hint: Read Section 4.6.)
5. (10 points). Consider the following AVL tree.
(see the pdf file or the handout for the figure)
(a) Show the tree after deleting node 150.
(b) Starting from the original tree, indicate a node for which
the deletion algorithm will require more than one rotation.
6. (10 points). Consider the same tree as the original one in Question 5 but now assume this configuration was obtained by using Splay tree insertion, find, and delete operations. Show the splay tree after the operation Find(240) and show it again after the subsequent operation Insert (50).