CSci 2101 Lab 12. June 20th.

40 points

Due Tuesday, June 21st.

Work in groups on this lab (the same groups as for Binary Search Tree).

Continue working on AVL trees. 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 tests that check if the tree rebalances correctly by checking teh 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 12. Make sure to CC your group partners.

CSci 2101 course web site.