You should have separate AVL and AVLNode classes as in Weiss's solution. Unlike Weiss's implementation, but as in Assigment 1, you should use a message-passing style rather than pass AVL or AVLNode objects as parameters to your methods. Unlike Weiss, you should not use default protection for the instance variables of the AVLNode class. You need only have a single constructor (with no arguments) for the AVL class.

Size queries should be implemented by providing a size() method for the AVL class that returns the number of nodes in the tree. Note that maintaining a size field for the node class will assist in finding the kth smallest element of the tree.

Finding the kth smallest element of the tree is to be done by a method getKthSmallest(int) that takes an integer k and returns the kth smallest element in the tree if one exists. If none exists (that is, if k is too large or too small), the method should return null. Your method should have time complexity O(log n).

Range queries are to be implemented by a method getRange(Comparable, Comparable) that returns, in sorted order, a List of all values in the tree between the given Comparable values, inclusive. If the first value is larger than the second, then you should return an empty list.

Your insertion method insert should allow duplicate insertion. It should take a Comparable argument and return no value. It should reject an attempted insertion of null.

Your traversal methods inorder() and levelOrder() should each return a List of all the Comparable values in the tree, in the appropriate order. You may use the methods provided in my solution to Assigment 2 for my Fall 2002 section of CS 146, with appropriate credit. Don't forget to credit Weiss for any methods that are substantially his. You may check my solution to Assignment 1 if you're having trouble with message passing; you needn't explicitly credit it.

For methods that return Lists, note that it is fairly inefficient to use the addAll method to concatenate lists, due to the copying required.

The message passing style is somewhat awkward in the case of height computations and rotations. The height computations are not difficult, although you might want to have a separate method that checks for imbalances during insertion. For the rotations, it may not be clear how to have a node rotate the subtree of which it is the root, since rotation changes the root. In this case, you may use the technique that we discussed for deletion from linked lists and from binary search trees, of moving keys from one node to another and updating links as necessary.

Note that if you maintain a size field in nodes, the rotation methods will have to update this field as well as the height field.

As always, you may define any other additional classes and methods (including constructors) that you find helpful. If you're stuck defining any method, consider a divide-and-conquer approach to the problem.