*********
AVL Trees
*********



*  In this lab we continue implementing our own data structure library.
*  You will implement the following UML in Java:

.. figure:: ./uml_avl.drawio.png
    :align: center

AVL - Start
===========

1.  Create a generic class :code:`BinarySearchTreeWithRotate`.

    *  It should inherit from :code:`BinarySearchTree`.
    *  And the generic type should also inherit from :code:`Comparable`

2.  Implement the following functions:

   *  :code:`rotateRight(E)`
   *  :code:`rotateLeft(E)`

AVL - AVL class
===============

1. Create the structure of the **generic** class :code:`AVLTree`.
   
   *  It should inherit from :code:`BinarySearchTreeWithRotate`.

2. Create the generic and static class :code:`AVLNode`.

   *  It should inherit from :code:`Node`.
   *  It contains only three constant data field.
   *  Implement the constructor.

3. Now finish the class :code:`AVLTree`.

AVL - Test
==========

You can use the following function to test your code:

.. code-block:: java
    :linenos:

    public static void avl_tree(){
        AVLTree<String> testOne = new AVLTree<String>();
        testOne.add("The");
        testOne.add("quick");
        testOne.add("brown");
        testOne.add("fox");
        testOne.add("apple");
        testOne.add("cat");
        testOne.add("hat");
        System.out.println(testOne.toString());

        AVLTree<Integer> testTwo = new AVLTree<Integer>();
        testTwo.add(30);
        testTwo.add(40);
        testTwo.add(15);
        testTwo.add(25);
        testTwo.add(90);
        testTwo.add(80);
        testTwo.add(70);
        testTwo.add(85);
        testTwo.add(15);
        testTwo.add(72);
        System.out.println(testTwo.toString());

        AVLTree<String> testThree = new AVLTree<String>();
        testThree.add("Now");
        testThree.add("is");
        testThree.add("time");
        testThree.add("for");
        testThree.add("all");
        testThree.add("good");
        testThree.add("men");
        testThree.add("to");
        testThree.add("come");
        testThree.add("to");
        testThree.add("the");
        testThree.add("aid");
        testThree.add("of");
        testThree.add("the");
        testThree.add("party");
        System.out.println(testThree.toString());