Download the template class and the driver

The template class has some useful functions for printing out your tree, so you should not modify these.

As usual, do not modify the driver.

As we will discuss in class, binary search trees are not optimal structures. In the worst case, a degenerate BST degrades to a linked list. Here we will be taking the first steps to implementing a self-balancing BST.

Create a class AvlTree. You AVL tree class should be a generic class containing Comparable items. In addition, AvlTree should have an internal class private AvlNode, also a generic container of Comparable items.

The internal AvlNode should have the following:

• Member variables:
  • left - The left child of this node.
  • right - The right child of this node.
  • parent - The parent of this node.
  • val - The (Comparable, generic) value that this node holds
• Constructors - A constructor that sets val and parent

AvlTree should have the following:

• Member variables:
  • root - The (AvlNode) root of the tree.
  • size - The number of nodes contained in the tree.
• Constructors - A default constructor that sets the root to null and the size to 0
• Methods:
  • size
    • return - The number of nodes in the tree.
  • insert - Inserts an element into the binary tree.
    • param
      • elem - The element to insert in the tree (element, NOT a node)
  • lookup - Finds if an element is contained in the BST
    • param
      • elem - The element to lookup
    • return - The element found within the tree. If the element is not found, return null
  • private rotateLeft - Performs a left rotation with the given node as the root.
    • param
      • node - The node at which to perform the left rotation.
  • private rotateRight - Performs a right rotation with the given node as the root.
    • param
      • node - The node at which to perform the right rotation.
• The methods nthBitSet and printAscii included within the template.

Here is a diagram of left/right rotations (taken from Wikipedia):

In the diagram, a right rotation is performed with Q as the root, while a left rotation is performed with P as the root.

The image was taken from this article, which you may find useful.

If you have trouble debugging your code, you may use the method "printAscii" included within the template. This will print an ASCII drawing of your tree.

      Lookup test succeeded.
      ----------------
      Rotation test:
         Jose
          |- Louie
          |  |- Nathan
          |  `- Kiley
          `- Jaki
             `- Beverly
      Left rotation around 'Jose'
         Louie
          |- Nathan
          `- Jose
             |- Kiley
             `- Jaki
                `- Beverly
      Right rotation around 'Jose'
         Louie
          |- Nathan
          `- Jaki
             |- Jose
             |  `- Kiley
             `- Beverly
      Right rotation around 'Louie'
         Jaki
          |- Louie
          |  |- Nathan
          |  `- Jose
          |     `- Kiley
          `- Beverly
      ----------------
      Randomized rotation test:
      Random tree:
         0
          `- 2
             |- 4
             |  `- 3
             `- 1
      Left rotation around 2
         0
          `- 4
             `- 2
                |- 3
                `- 1
      Right rotation around 1
         0
          `- 4
             `- 2
                |- 3
                `- 1
      Right rotation around 2
         0
          `- 4
             `- 1
                `- 2
                   `- 3
      ----------------
      

Upload the .java file to the dropbox