=============================================================================
       CSC 263                Tutorial 4               Winter 2019
=============================================================================

In this tutorial, will learn about AVL-Delete using various examples. 

1. Consider the following AVL tree, what happens if we insert a node 5 into the
tree? Which node is the lowest ancestor to become unbalanced? What type of
rotations need to be performed to rebalance the tree? Perform the AVL-INSERT
carefully step by step.

         3
       /   \
      2     7
     /     / \
    1     4   8
           \
            6

2. Consider the following AVL-tree, what happens if we delete the node 8 from
the tree? What type of rotations are needed to rebalance the tree? What's the
height of the tree before deletion? What's the height of the tree after
deletion?

         6
       /   \
      4     7
     / \     \
    2   5     8
   / \
  1   3

3. Consider the following AVL-tree, what happens if we delete the node 2 from
the tree? What type of rotations are needed to rebalance the tree? What's the
height of the tree before deletion? What's the height of the tree after
deletion?

         3
       /   \
      2     7
     /     / \
    1     5   8
         / \
        4   6

4. Come up with an example AVL-tree for which deleting a node from the tree
causes two levels of double-rotations.


5. Draw a picture of the structure of the AVL tree for which deleting a node
would cause O(log n) rotations, where n is the number of nodes in the tree.

6. Suppose in the AVL-INSERT operation, the tree looks like the following right
after inserting the new node and before rebalancing. 

   1
    \
     2
      \
       3
        \
         4

Since node 2 is the lowest ancestor that is unbalanced, we do a left
rotation around 2, which gives us the following tree

   1
    \
     3
    / \
   2   4

This tree is still not AVL, which contradicts with what we said in the lecture
that AVL-INSERT requires only one level of rotation. What went wrong?