Programming question for Homework 2: AVL Trees

Implement a dictionary class. The dictionary should be implemented as a height-balanced balanced binary search tree (an AVL tree), encapsulated in a class called AVLTree. The provided starter code implements an ordinary binary search tree; you must revise this code to implement an AVL tree. Your implementation should be consistent with the algorithms described in the "AVL tree notes" handout posted on the course website.

This implementation of an AVL tree will use a simplified Node class to store information at each node of the tree. Each node will store an integer key, integer data, references to the parent, left child and right child, and an integer balance factor bf.

You should implement the following methods of the AVLTree class (described in the starter code):

• singleLeftRotation()
• singleRightRotation()
• doubleRightLeftRotation()
• doubleLeftRightRotation()
• balance()

You should also alter the following methods of the AVLTree class to support the update of node balance factors and, when necessary, appropriately call the balance() method:

• treeInsert()
• delete()

The delete() may require significant rewriting. During an insert or delete, all necessary updates of node balance factors must be completed in O(log n) total time, where n is the number of nodes in the tree following the operation. The worst-case time complexity of balance() and each of the rotation methods should be O(1).

To mark your assignment, we will test the above methods using our own secret tester routine. Successfully running the AVL class we provide does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own test cases. Your code may be tested with an auto-marker routine and/or by TA inspection to check that your routines are implemented correctly (as described in the comments or the "AVL tree nodes" handout) and in the correct time bounds.

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the AVLTree class, where indicated by comments that start with: "// TODO:". You may also add appropriate private instance variables or helper methods.

Starter code:

• AVLTree.java
• Node.java

The code in AVL.java creates an AVL tree and executes basic operations on it. The sequence of operations and their arguments are read from the input in the form of user-defined commands. The commands supported are add, delete, search and print. This class may be useful for testing your code.

• AVL.java

Submission Instructions

1. Submit your code using the "submit" mechanism on fissure (by 6:00pm on Friday, July 4). Use the following command from the directory containing your solution:
   submit -N p2 cscb63s AVLTree.java
   The command "man submit" contains general instructions for submitting your code electronically.
   
2. Submit only the .java file AVLTree.java of the starter code (after you have implemented the missing parts). All the code that you implement should be inside this file.


3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.


4. Do not submit any printout of the code.


5. Do not rename the file AVLTree.java, or any of the methods and variables found in our starter code.


6. Write your name, student number and username in a comment at the top of the AVLTree.java file.


7. We will compile your code by typing "javac AVLTree.java" and we will test the resulting .class file(s) using our own tester code (which is similar to, but more thorough than, the tester code that we provide as part of the starter code).


8. Your code must compile and run on the fissure system. Test it there! Programs that do not compile and run get 0 marks.