Lab 11 - AVL Tree (04/12/2021)

References

avl.pptx

FAQ

Files

Description

"In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations."

Learning Outcomes

By completing the AVL Tree Lab, you will be able to:

Determine if a Binary Search Tree is critically imbalanced and distinguish between the various types of imbalance.
Implement functions to rotate nodes and balance a Binary Search Tree.
Insert and remove nodes from a Binary Search Tree while maintaining tree balance.

The Lab

Lab Requirements:

There are multiple correct methods for rebalancing nodes in an AVL tree; each method may result in a unique tree. Some conventions will need to be used to ensure that your tree properly matches ours. For this class, you should follow the algorithms presented in the course text, starting on page 634.
- For example, when a Node is left-imbalanced and its left child is balanced, treating it as a Left-Right case will produce a "balanced" tree, but it would be different from the expected output and would be marked as incorrect. You should treat this as a Left-Left case.
- When removing a node with 2 children, replace it with its in-order-predecessor, or "greatest left child."
Remember to disallow duplicate entries and handle the case where the element to be removed is not in the tree.
You should remove nodes from the AVL tree in the same manner used in the BST lab.
You are required to make your AVL a template class.
You may not use any Standard Library data structures.
The AVL code used in the textbook can be hard to follow. Feel free to ask the TA's for help and ideas.
The following summarizes the commands used in the AVL lab:

COMMAND	DESCRIPTION	OUTPUT
INT	Instantiates a AVL object for subsequent commands.	true
STRING	Instantiates a AVL object for subsequent commands.	true
add <data>	Add data node to AVL. Return false if duplicate.	true false
remove <data>	Remove node from AVL. Return false if not found.	true false
clear	Delete all nodes from the AVL.	true
size	Output the number of nodes in the AVL.	Number of AVL nodes
print	Print AVL (using insertion operator) in level-order.	Level-order listing of AVL
find <data>	Find node in AVL. Return "found" or "not found".	found not found

Steps to Success:

Step 1 - Start with the code you already have from the BST lab.
1. An AVL Tree is a BST but with added functionality for balancing, so much of the code you already have for BST will also be used in this lab. Input files are in the same format as in the BST lab, so you could keep the same parsing code that you used in your BST main file, but the output will be formatted slightly differently.
Step 2 - Update your Node class.
1. To balance a tree, you need to be able to get the height of a node. You may find it helpful for debugging to implement a recursive getHeight() function in your Node class, but keep in mind that doing so decreases the efficiency of adding and removing nodes. A more efficient algorithm may be to have a height variable with a constant-time updating function called on it at appropriate instances.
Step 3 - Add rotation and balancing functionality.
1. Begin by adding rotateLeft() and rotateRight() functions to your tree class. Then test them to ensure they work properly.
2. Now, add a balance() function to the tree class that uses the getHeight() function to determine if a node is critcally imbalanced. If there is a critical imbalance, perform the appropriate rotations. Test your balance function to ensure it works properly.
Step 4 - Update insert() and remove() so that they rebalance the tree.
1. If you used recursion to write these functions originally, this will only require trivial changes. Immediately after the insertion or removal, you will recurse back up to every previous node that you visited to perform the insertion or removal. All you have to do is balance each node on the way back up through the recursion.
2. After updating each function, test it to make sure it works properly.
Step 5 - When you've successfully implemented and tested each part, try running your code with the provided test cases.

Helps and Hints

Note: Code examples come from readily available, public websites (ie., stackoverflow.com, cplusplus.com, etc.)

Online AVL Visualization:

A website has been created to help you visualize AVL Tree algorithms. You can find it here.

Online BST Visualization:

You can find Wikipedia Binary Search Tree algorithms here.

Level Order Traversal of a BST._(collapse)

A binary tree is one where each node has at most two children, named left and right. The level of a tree is the number of parent nodes a tree node has. Thus, the root of the tree is at level 1. The root's children are at level 2, grandchildren are at level 3, etc.

Trees can be traversed in level-order by visiting every node on a level before going to a lower level.

/** Output nodes at a given level */
bool outLevel(Node<T>* root, int level, stringstream& out) const
{
   if (root == NULL) return false;
   if (level == 1)
   {
      out << " " << root->data;
      if ((root->left != NULL) || (root->right != NULL)) return true;
      return false;
   }
   if ((level == 2) && !root->left && root->right) out << " _";
   bool left = outLevel(root->left, level - 1, out);
   bool right = outLevel(root->right, level - 1, out);
   if ((level == 2) && root->left && !root->right) out << " _";
   return left || right;
} // end outLevel()

/** Return a level order traversal of a BST as a string */
string toString() const
{
   stringstream out;
   if (root == NULL) out << " empty";
   else
   {
      int level = 0;
      do
      {
         out << endl << "  " << ++level << ":";
      } while (outLevel(root, level, out));
   }
   return out.str();
} // end toString()

Understanding Valgrind Output._(collapse)

You can find helpful hints and explanations of Valgrind output here.

AVL Tree Grading

Instructions for submitting your lab:

Zip all your lab source files (.cpp, .hpp, .h) into one folder. DO NOT INCLUDE YOUR WHOLE PROJECT!
Submit your zipped lab source using the "Labs" tab on the class website.
Your submitted lab source will be compiled and executed using a lab gcc compiler.
Both input and output files will be specified by command line arguments.
An auto-grader will compare your output files with expected results and you will shortly receive an accumulative score.
The auto-grade process may abort on the first error. If so, correct the error and try again.
You may re-submit your zipped source as many times as you like.

Use the following input and resulting output files in testing the AVL Tree lab.

	Input File	Output File
Test #1	lab11_in_01.txt	lab11_out_01.txt
Test #2	lab11_in_02.txt	lab11_out_02.txt
Test #3	lab11_in_03.txt	lab11_out_03.txt
Test #4	lab11_in_04.txt	lab11_out_04.txt
Test #5	lab11_in_05.txt	lab11_out_05.txt

The auto-grader will be expecting to find in your output file the following sections:

Fail	Pass	Auto-graded Section Requirements (40 points)	Score = 0
		Your AVL tree passes lab11_in_01.txt. (lab11_in_01.txt).	8 points
		Your AVL tree passes lab11_in_02.txt. (lab11_in_02.txt).	8 points
		Your AVL tree passes lab11_in_03.txt. (lab11_in_03.txt).	8 points
		Your AVL tree passes lab11_in_04.txt. (lab11_in_04.txt).	8 points
		Your AVL tree passes lab11_in_05.txt. (lab11_in_05.txt).	8 points
		Memory leaks, g++ compiler warnings, array out-of-bounds, or use of STL container detected.	-10 points

Total Score = 0

Your lab will not be peer reviewed.

No	Partial	Yes	Peer Review	Score = 0