CPSC 220 Fall 2005
HW 11: More AVL Trees

1. Create the tree from L&C Exercise 13.3, that is, the AVL tree you get by inserting the integers (34 45 3 87 65 32 1 12 17). You can just use the tree from class; no need to show your work in recreating it. Then show the AVL tree you get by deleting (87 65). Show your work as you rebalance as necessary after each deletion.

2. Show the AVL tree that you get by inserting integers 1-10 in order into an initially empty tree. Show your work, including all rotations.

3. Start with the tree you built in #2, then show the tree you get by removing (1 2 8 10). Be sure to rebalance as necessary after each deletion.

4. After doing a single insertion into an AVL tree, is it possible that you will have to do more than one rotation to bring the tree back into balance? (Consider a leftright or rightleft rotation as just one.) If so, give an example. If not, explain why not. Hint: How does initially inserting a node affect the height of the tree or of relevant subtrees? What about after a rotation, if one is needed? You may find it helpful to study the diagrams on p. 411-415. Remember that each of these trees may be a subtree of a larger tree.

5. After doing a single deletion from an AVL tree, is it possible that you will have to do more than one rotation to bring the tree back into balance? (Consider a leftright or rightleft rotation as just one.) If so, give an example. If not, explain why not. Hint: How does initially deleting a node affect the height of the tree or of relevant subtrees? What about after a rotation, if one is needed? You may find it helpful to study the diagrams on p. 416. Remember that this could be a subtree of a larger tree.