5. AVL Trees

  • In this lab we continue implementing our own data structure library.

  • You will implement the following UML in Java:

../../_images/uml_avl.drawio.png

5.1. AVL - Start

  1. Create a generic class BinarySearchTreeWithRotate.

    • It should inherit from BinarySearchTree.

    • And the generic type should also inherit from Comparable

  2. Implement the following functions:

  • rotateRight(E)

  • rotateLeft(E)

5.2. AVL - AVL class

  1. Create the structure of the generic class AVLTree.

    • It should inherit from BinarySearchTreeWithRotate.

  2. Create the generic and static class AVLNode.

    • It should inherit from Node.

    • It contains only three constant data field.

    • Implement the constructor.

  3. Now finish the class AVLTree.

5.3. AVL - Test

You can use the following function to test your code:

 1public static void avl_tree(){
 2    AVLTree<String> testOne = new AVLTree<String>();
 3    testOne.add("The");
 4    testOne.add("quick");
 5    testOne.add("brown");
 6    testOne.add("fox");
 7    testOne.add("apple");
 8    testOne.add("cat");
 9    testOne.add("hat");
10    System.out.println(testOne.toString());
11
12    AVLTree<Integer> testTwo = new AVLTree<Integer>();
13    testTwo.add(30);
14    testTwo.add(40);
15    testTwo.add(15);
16    testTwo.add(25);
17    testTwo.add(90);
18    testTwo.add(80);
19    testTwo.add(70);
20    testTwo.add(85);
21    testTwo.add(15);
22    testTwo.add(72);
23    System.out.println(testTwo.toString());
24
25    AVLTree<String> testThree = new AVLTree<String>();
26    testThree.add("Now");
27    testThree.add("is");
28    testThree.add("time");
29    testThree.add("for");
30    testThree.add("all");
31    testThree.add("good");
32    testThree.add("men");
33    testThree.add("to");
34    testThree.add("come");
35    testThree.add("to");
36    testThree.add("the");
37    testThree.add("aid");
38    testThree.add("of");
39    testThree.add("the");
40    testThree.add("party");
41    System.out.println(testThree.toString());