CSE 326, Spring 1997: Homework 4

Due 4/30/97

(10 points) In this problem we will explore the problem of how many nodes are in an AVL tree of height d.
- For d = 1,2,3,4 construct an AVL tree of height d with a minimum number of nodes.
- Find an expression for the minimum number of node in an AVL tree of height d.
(20 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 20 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      12  18            40
                     /
                   11
```