lab_avl

Assignment Description

In this lab we’ll practice AVL tree rotations and insertions, and see some silly test cases.

Lab Insight

AVL trees can be used to build data structures like sorted maps and sets. To be quite honest, Red-Black trees, another kind of self-balancing search tree, are used more often in these applications because inserting things into them is faster. However, the general search performance of AVL trees is better, and even though AVL trees sound complicated to implement, all they need is a careful implementation of rotations to work well. Either way, the general principle of using self-balancing trees for data is useful because it helps search for things in faster than the O(n) time we would need if all we had were linked lists. Without rolling the dice and hoping for the best (an actually workable strategy, as we will see in later data structures), balanced trees are the go-to for good worst case search performance. They are the basis for many other data structures (like the maps and sets we mentioned before) and algorithms (they’re better than naive lists if we’re going to be searching for things), and a useful data structure to have in our toolkits for a lot of problems.

Checking Out the Code

All assignments will be distributed via our release repo on github this semester. You will need to have set up your git directory to have our release as a remote repo as described in our git set up.

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main --allow-unrelated-histories
git push

The first git command will fetch and merge changes from the main branch on your remote repository named release into your personal. The --no-edit flag automatically generates a commit message for you, and the--no-rebase flag will merge the upstream branch into the current branch. Generally, these two flags shouldn’t be used, but are included for ease of merging assignments into your repo.

The second command will push to origin (your personal), which will allow it to track the new changes from release.

You will need to run these commands for every assignment that is released.

All the files for this lab are in the lab_avl directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the lab_avl directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

Implement Rotation Functions

You must implement rotateLeft(), rotateRight(), and rotateRightLeft(). We have implemented rotateLeftRight() for you as an example for implementing rotateRightLeft().

Implement the rebalance() Function

You must implement rebalance() function. rebalance() should, given a subtree, rotate the subtree so that it is balanced. You should assume that the subtree’s left and right children are both already balanced trees. The node’s height should always be updated, even if no rotations are required.

Implement the insert() Function

You must implement the insert() function. insert() should add a node with a key and value at the correct location in the tree, then rebalance appropriately (while returning from each recursive function) to fix the tree’s balance.

Implement the remove() Function

You must implement the remove() function. remove() should remove the node with the specified key from the tree, then rebalance appropriately (while returning from each recursive function) to fix the tree’s balance. You can assume that the key exists in the tree. You may want to use the swap() method.

Testing Your Code

To test your code, compile using make:

make

Then run it with:

./testavl color

You will see that the output is colored — green means correct output, red means incorrect output, and underlined red means expected output that was not present. This mode is a bit experimental, and it might cause problems with your own debugging output (or other problems in general). To turn it off, simply leave off the “color” argument:

./testavl

You may also diff your solution with our expected output:

./testavl | diff -u - soln_testavl.out

Type [Escape] [:] [q] [a] [ENTER] to exit vimdiff.

To make the catch test suite, run:

make test

After compiling the test suite, run the tests using:

./test

Submitting Your Work

The following files are used in grading:

• avltree.hpp
• avltree.h

To submit your assignment you upload these file to the lab_debug question on PrairieLearn. All other files including any testing files you have added will not be used for grading.