5. AVL Trees
In this lab we continue implementing our own data structure library.
You will implement the following UML in Java:
5.1. AVL - Start
Create a generic class
BinarySearchTreeWithRotate
.It should inherit from
BinarySearchTree
.And the generic type should also inherit from
Comparable
Implement the following functions:
rotateRight(E)
rotateLeft(E)
5.2. AVL - AVL class
Create the structure of the generic class
AVLTree
.It should inherit from
BinarySearchTreeWithRotate
.
Create the generic and static class
AVLNode
.It should inherit from
Node
.It contains only three constant data field.
Implement the constructor.
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());
ENSURE WE HAVE RECORDED YOUR COMPLETION. FAILURE TO DO SO WILL RESULT IN A GRADE OF 0!