CSE 326, Winter 1999: Homework 4

Due 2/12/99

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual)and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Staight pseudocode with no additional documentation is not enough.

1. (10 points) In this problem you will design a recursive AVL deletion procedure and execute it on a simple example.
   • Design a recursive AVL tree deletion procedure. You may assume that rotation and height calculation procedures are available to you. Your procedure should be modeled on the deletion procedure of lecture 8, slide 9 and the description of AVL deletion given in lecture 10.
   • Demonstrate your algorithm by doing all the rotations needed to delete 10 from the following AVL tree. If there is more than one rotation show the result after each rotation.

                                 20
                             /        \
                          10           30
                        /    \       /   \
                       5     15    25     35
                     /  \      \            \
                    3    7     18            40
                          \  
                           9
     

2. (10 points) In this problem you will define a recursive top down splaying function. Given a splay tree T and a key x, top down splaying will move x (or if x is not in the tree, the successor or predecessor of x) to the root two levels at at time except for possibly one time moving one level. To splay T at the key x there are three cases. Case 1: x or the node where x would be inserted is at the root of T. In this case there is nothing to do, just return. Case 2: x or the node where x would be inserted is one level from the root of T. In this case simply rotate that node to the root. Case 3: x or the node where x would be inserted is at least two levels from the root. Now there are four subcases depending on the direction from the root the path to x follows. We consider just one of the four subcases, as the others are similar. Suppose the path to x or where x would be inserted is first right, then left. Replace T.right.left with the result of recursively top down splaying T.right.left at the key x. Now, double rotate to move x to the root (a right-zig-zag subcase).

   You can assume that you have functions right-rotate(n : reference node pointer) and left-rotate(n : reference node pointer) that rotate from the right and left, respectively.

   Show the result this top down splaying at 8 in the tree above.