## CPSC 220 Fall 2005

HW 11: More AVL Trees

- 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.

- 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.

- 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.

- 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.

- 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.