AVL Trees

This lab will explore AVL Trees.

(Based on a lab developed by Michael Kirkpatrick)

Starter Code

• AVLNode.java - Sub-class of a BinarySearchNode that provides functionality for a node in an AVL tree. UNFINISHED!
• AVLTree.java - Sub-class of a BinarySearchTree that provides the method for inserting a node into an AVL tree.
• BinarySearchNode.java - OpenDSA implementation of a node for a binary search tree, modified to include rotation methods. UNFINISHED!
• BinarySearchTree.java - OpenDSA implementation of a node for a binary search tree, modified to include an Iterator and toString method for debugging.
• SearchNode.java - OpenDSA interface of a node in a search tree. Also supports non-binary 2-3 trees.
• SearchTree.java - OpenDSA interface of a node in a search tree. Also supports non-binary 2-3 trees.

Tree Node Rotations

Start by implementing the rotateLeft and rotateRight methods in BinarySearchNode. See the comments in the code for more details.

AVL Trees

The AVLNode and AVLTree classes inherit the binary search tree functionality for inserting a new value in the correct place. However, the result might be an unbalanced tree. Implement the recursive rebalance method in AVLNode to keep the AVL tree balanced. See the comments in the code for more details.

Testing code

• BinarySearchTest.java - Tests for the tree rotations.
• AVLTest.java - Tests for the AVL re-balancing algorithms.
• TreeRunner.java - Main runner class to experiment with inserting values into a tree and observing the results.

The TreeRunner class contains a main method where you can build trees and observe the logical structure. For each node in the tree (assuming that the tree is structured to allow in-order traversals), there will be a line of output of the following format:

7 [P: 3; L: 5; R: -]

This line indicates that there is a node storing the value 7, its parent node stores the value 3, and it has a left child storing the value 5. The - is used to indicate null values. In this case, it indicates that the current node has no right child. If the parent node is -, then the current node is the root. AVL tree nodes contain additional information to indicate the height (HT) of the sub-tree rooted at that node, along with the node's balance factor (BF).