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