CSE 373, Autumn 2002: Homework 4

Due 11/1/2002

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. Straight pseudocode with no additional documentation is not enough. Your pseudocode can contain English if needed. Each problem should be answered on a separate sheets of paper so they can be graded by different TAs. Your name should be at the top of every page.

(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 recursive deletion procedure on page 115 of the text. After each recursive call and before returning, rotations must be done to rebalance the tree. See the way this is done for AVL tree insertion on page 128 of the text.
- 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 single or double rotation.
```
                            20
                        /        \
                     10           30
                   /    \       /   \
                  5     15    25     35
                /  \      \            \
               3    7     18            40
                     \  
                      9
```
(10 points) In this problem you will demonstrate how splay tree insertion and deletion work on the example tree above.
- Insert 8 into the tree above. Show the tree after each rotation and double rotation.
- Delete 10 from the tree above. Show the tree after each rotation and double rotation.