AVL Trees Paper Exercises:


1. Devise concrete examples of binary search trees that must be balanced
   by EACH of the following AVL rotations:

     LL, RR, LR, and RL

   Each of your 4 examples must consist of at least 5 nodes.



2. Insert the following elements, in order, into an AVL tree.  Indicate
   the type of rotation, if any,  needed to balance each insertion:

   7 8 6 5 4 3 2 1 9

   Show work.



(3, 4 you should finish after delete)
3. Show the resulting tree after deleting the root element from the tree.




4. Devise an example of deletion from an AVL tree that would require 
   two separate LL rotations to maintain balance.



---------------------


Lab exercise : 


A.  Modify the avlnode class to keep statistics of the number of LL,
    RR, LR and RL rotations made during insertion.  Write a program to
    insert the numbers 1 2 3 4 ... 2048 into a tree, and collect the
    statistics.  Then insert 2048 randomly generated integers into an
    AVL tree, and again collect the statistics.  Be sure that the
    random integers are of a sufficiently large range.  If there are
    discrepancies between the numbers from the two experiments, can
    you explain them?  Can you form generalized conjectures from the
    statistics that you've collected?  Run other, similar experiments
    if necessary.  Hint: use static class-variables to count the rotations.
 
A2  (slight challenge) Devise an experiment that will involve more
    rotations than the either of the above experiments (using again 
    2048 insertions).


B.  Test the performance of AVL trees.

    C1: insert the numbers 1 2 3 4 ... 50000 in order into both a regular
    BST (node) and an AVL BST. record the time it took to determine that
    50001 is not in the tree. Increase the sizes of the trees if necessary
    to obtain meaning measurements.

    C2. This time, insert 50000 randomly generated numbers into a tree,
    then again look for something that isn't in the tree (using a number
    that's outside of the range of random number generation).  Record
    difference in times observed between a regular BST and an AVL BST.
    Make sure that the range of random numbers is amply large.

    What can you conclude from the two experiments?


C.  The AVL insert procedure I gave you is not optimized (though it is
    of log n complexity).  The "balance" procedure is always called after
    a recursive call to insert.  So each node "up the tree" is balanced
    after some node is added.  Theoretical consideration of AVL trees
    show, however, that at most one of the 4 rotations will be needed after
    each insertion (we consider RL and LR as distinct from LL and RR).

    Your task is to optimize the avlnode.insert method to eliminate 
    redundant calls to balance().  Hint: you can use a counter, but
    don't forget to reset it.