Here is Wikipedia's page on AVL Trees. This page contains nice, colored pictures showing the two possible single rotations and the two possible double rotations. To implement an AVL tree, you should first define an AVLNode class. Recall that each binary tree node had 3 fields: a key field, a leftChild field, and a rightChild field. An AVLNode object may have two additional fields:

1. height: that keeps track of the height of the subtree rooted at that node.
2. balance: that keeps track of the balance of the node.

Problem: Based on this description and our class discussion, implement an AVLNode class. Then implement an AVLTree class with the find method and a ``skeleton'' of the insert method. The find method is easy to implement because searching an AVL tree is no different from search a binary search tree.

The insert method in an AVL tree has the following steps:

1. Search for the given key in the AVL tree. Let us assume that the given key is not found in the AVL tree. The search path is defined as the sequence of nodes visited, starting at the root, by the search method before reaching null.
2. Walk back along the search path until a node is found whose balance is not +1, -1, or 0. Call this node the pivot node. As we walk back along the search path, we update the height and balance fields of all the nodes in the search path.
3. Perform a single rotation or a double rotation at the pivot. As discussed in class, there are four cases: two symmetric cases that use single rotation and two symmetric cases that use double rotation.