22C:21: Computer Science II: Data Structures

Problem Set 9. Posted 4/19. Due on 4/27.

Notes: Problem 1 is your homework and it is due at finals time (Tuesday, May 8th, noon-2 pm). Of the remaining two problems, one will be solved by your TA in the discussion section meetings on Thursday 5/3. The remaining problem will be your quiz; this will occur at the end of the discussion section meeting (on 5/3), you will have 20 minutes for the quiz and you are allowed to consult your notes and textbook.

  1. Add a post order tree iterator to the generic binary search tree class you implemented for Problem Set 8. Mimic the implementation of an in order tree iterator described in class.

  2. Add the following two functions to this binary search tree class.
    1. int height()
      This function returns the height of the tree.
    2. boolean isAVL()
      This function returns a boolean value indicating if the tree is an AVL tree or not.

    It makes sense for both of these functions to be wrapper functions that simply call other recursive functions.

  3. Start with an empty AVL tree and insert the items 
    	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    in that order, into the tree. For each insertion show the following information. Suppose that T is the current tree and x is the new item being inserted.
    1. Show the new tree, let us call this T', obtained by inserting x. Show the balances of all the nodes and indicate if T' is an AVL tree or not.
    2. If T' is not an AVL tree, specify how to fix it. The choices are (i) single left rotation, (ii) single right rotation, (iii) a double rotation in which we first perform a left rotation and then a right rotation, and (iv) a double rotation in which we first perform a right rotation followed by a left rotation.
    3. If T' is not an AVL tree, turn it into an AVL tree by performing the operation specified above. Show the tree after the operation has been performed and show the balances of all the nodes so that it is clear that the resulting tree is an AVL tree.