CSSE 230: AVL Trees - Part 1

• Work on this project by yourself.
• Create a new project called AVLTreeProject.
• Create an AVLTree class in which you implement an AVL tree. In particular, please implement the four rotations as specified for AVL trees. Please ensure that you actually rotate the nodes. Do not create new nodes!
• As before, you are not permitted to have a field in your BinaryNode class that points to its parent. As a matter of fact you are permitted just four fields in the BN class: for the element, the lefChild, the rightChild and the height.
• You only need to maintain an inOrder and a preOrderIterator.
• Please modify your pre-order iterator so that it returns a BinaryNode object.
• Feel free to copy your code from the BST projects into the AVLTreeProject and modify it. Please maintain height information at each node rather than balance information.
• For now, focus on implementing the insert() method. Please ensure that it is recursive and that the recursion takes place in the BinaryNode class. This method has to run in O(log(n)) time.
• Add a getRotationCount() method. This methods returns the number of single rotations performed during an insertion/removal sequence. A double rotation counts as two rotations.
• I will eventually ask you to add a remove() method.
• Please use the test-suite as well as test cases of your own design to test your software.
• Please ensure that your code is efficient, i.e. ensure that your insert and remove methods run in O(log(n)) time and the size and height methods run in O(1) time.
• Design and develop your code using good style and implementing it so that it runs in an efficient manner. In particular,
  • Review your code and ensure that it is well written.
  • Look for places where you can simplify your code through code reuse and other methods.
  • Continue to use inner classes.
  • None of the methods in the AVLTree class proper should be recursive. Recursion should only take place in the BinaryNode class.
  • Ensure that your code follows true OO-style, i.e. except for some support functions, by and large do not pass in the object to which you apply a method.
  • Use good function decomposition, i.e. avoid spagetti code.
  • You are not permitted to us a Null Node object. Please use null pointers instead.
  • Please remove dead code, do not just comment it out, just remove it. There is one exception. The Testing.java code needs to run with the getters and setters disabled. However, you may keep the getters so that the Treevisualizer works.
  • Please incorprate the feedback we gave you on prior assignments to ensure your code is in ship-shape.
  • Violating these principles of good code design may result in a deduction of up to 50 points.
• This is a multi-part exercise.