CSci 2101 Lab 13. November 15th.
50 points
Due Monday, November 21st.
Work in groups on this lab (as assigned).
Your goal is to implement and test an AVL tree (a self-balancing tree).
As a minimum requirement you need to:
- Implement the general set-up for the AVL tree (the node class, extra
instance variables, etc)
- Add a heigth method to check the height of a node.
- Write JUnit tests that check if the tree rebalances correctly by
checking the height. You will be better off writing smaller tests
that check a particular functionality. See next item for more details
on where to start.
- Implement put method that rebalances the tree for at least two
cases, one linear (e.g. LL) and the other one zigzag (e.g. RL).
Extra credit:
- Test and implement all four rotations.
- Test and implement (or start on) a remove method that leaves the tree
balanced.
How to submit
Submit
the java file(s) with your testing code by e-mail to me. The subject of the message
must
be 2101 Lab 13. Make
sure to CC your group partners.
CSci 2101 course web site.