Week 14: Lab Document, 12/6
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:
- height: that keeps track of the height of the subtree rooted at that node.
- balance: that keeps track of the balance of the node.
An AVL tree can be then viewed a collection of AVLNode objects satisfying the binary search tree
property and in addition the AVL property (i.e., the balances of all nodes should be
+1, -1, or 0).
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:
- 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.
- 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.
- 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.
By a ``skeleton'' of the insert method, I simply mean an implementation that
performs Steps (1)-(2).