Questions on Balanced Search Trees

This assignment is to be done individually, without a partner. You may share ideas with others in the class, but you should turn in your own assignment. Turn in your answers electronically. Most of this assignment involves drawing trees, which is faster and easier to draw by hand than to use software. Feel absolutely free to write out your solutions by hand, and scan using a scanner at the library (or elsewhere) before submitting. You're also welcome to draw them using software if you like.

1. Draw the AVL tree that results after inserting, in this order, the following words:

   the
   meaning
   of
   life
   universe
   and
   everything
   is
   forty
   two
   

   Show each AVL tree after each insertion. In other words, you should be submitting drawings of 10 trees, each one of which has successively one additional item in it.

2. Repeat the above exercise, but use a 2-3 tree instead of an AVL tree.
3. Page 479 of your textbook lists the four different ways in which an AVL tree can go out of balance. For each case, once you have performed either a single or double rotation at the lowest misbalanced node, explain why you do not need to perform further rotations higher up the tree. Or, to say it differently: explain why a single fix (either a single or double-rotation) is sufficient to fix a balancing problem; the need for further rotations does not percolate up the tree further.