Lab: 34 - AVL Trees

Assigned

Friday, 17 November 2023

Overview

The objective of this lab is to insert elements into an AVL Binary Search Tree (BST) while maintaining the height balance of AVL nodes. Recall that 4 kinds of insertion may violate the balance property (see Weiss 19.4). Restoring the balance of the AVL trees requires single or double rotations.

This lab focuses on restoring the AVL tree balance for two out of four cases of inserting elements into the AVL trees.

Preparation

Before you start the lab use the data structures visualization program from the University of San Francisco to compare BST vs. AVL Trees. Write down a sequence 10 numbers “at random” and use that same sequence to visualize a BST and then an AVL tree. Notice the difference in behavior upon insertion of a new number and how the final shape of the trees differs.

Create a new Eclipse project and import the files in this subdirectory: /home/jimenezp/csc207/Lab-AVLTree

Take the time to read through the code and understand what it is doing. You might try sketching images as you read and work through some insertions into trees. Look for the sections marked with “TODO”.

Also create a client/testing program that will create several trees for testing.

AVL Nodes

An AVL tree consists of AVL nodes that are defined in the AVLNode class. Each node has 3 fields: iData, for storing an element, leftChild and rightChild that reference the left and right child nodes. In addition, an AVLNode object has two other fields:

1. height: it keeps track of the height of a subtree rooted at this node.
2. balance: it keeps track of the balance of the node.

AVL Tree

An AVL Tree can be viewed as a collection of AVLNodes that satisfy the balance property in addition to the binary search order property. For this lab, we define the balance of an AVL Node object as:

balance = height of right subtree – height of left subtree

An AVLNode is balanced if its balance is +1, -1, or 0. Otherwise, that node is imbalanced.

1. (1 point) The AVLTree class has a public find method. This method accepts an element as a parameter and checks if that element exists in the tree. If the element is found, the find method returns an AVLNode that contains the element. Otherwise, it returns null. TODO Implement the find method in AVLTree class as a non-recursive (iterative) method. Use the binary search order property to implement this method.
2. (2 points) The insert method performs the following steps to place an element into the tree:
   1. Given that the AVLTree is not empty, it checks if the element is already in the tree. If so, it returns IllegalArgumentException. Otherwise, it creates a new AVLNode. The insert method places the given element into an appropriate position using a search path. The search path is a sequence of nodes, starting at the root, that are visited before reaching null. To store the search path, the insert method pushes the visited nodes into an AVLStack. so that the path from the root to the inserted node is kept on the stack.
   2. TODO A parent node is used to identify the parent of the new node. Use the parent node to place the new node at the appropriate position. The insert method code has a placeholder on lines 61 to 63 to specify the insertion point.
   3. After inserting the new element, the insert method walks back along the search path to check the balance of AVLNodes as defined above. This is done by extracting elements from AVLStack starting from the parent of the newly inserted node.
   4. If a node is imbalanced, the insert method performs a single or double rotation at the imbalanced node.
   5. After performing an appropriate rotation, the insert algorithm walks back along the search path to update the balance and height fields of AVLNodes that are in AVLStack. These nodes are on top of the recently inserted node.
   6. TODO Complete the previous step 2.5 (the rotations) when an AVLTree is imbalanced for two cases of insertions: 1) The new element is inserted at the left subtree of the left child of the imbalanced AVLNode, or 2) The new element is inserted at the right subtree of the left child of the imbalanced AVLNode.
      • To restore balance, you need to call either rotateWithLeftChild method for case 1 or the doubleRotateWithLeftChild method for case 2. (These methods are already implemented in the AVLTree class.) After returning from these methods, AVLNode(s) whose balances are changed after doing the rotations need to be pushed into AVLStack. Eventually, the height and balance fields of the imbalanced nodes will be corrected.

Finally, test your program by building three AVLTrees with these sequences of integers. For each sequence, call the displayTree method to display the AVLNodes of an AVLTree after inserting an integer. You might also run the simulation program from the University of San Fransisco to see what the AVL tree is doing in the background.

• Tree 1: 20, 15, 10
• Tree 2: 20, 15, 17
• Tree 3: 20, 15, 17, 10, 8

In this lab you inserted nodes into the left subtree (or an empty tree); so you were only asked to write code to handle Case 1 and Case 2 of Weiss’s four cases. The right side is roughly the same but with left and right interchanged.

Lab Submission

Submit AVLTree.java and your Tester class along with the output after running your program (1 point).

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.