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.
- Notice that the iterator() method of the testcode invokes a
pre-order iterator. Please make the appropriate change. Also
notice that the iterator has to be generic, i.e. it needs to implement
Iterator<T>
- 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
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.