Lab AVL

Assignment Description

In this lab we’ll practice AVL tree rotations, insertions, and deletions. This is a great exercise to practice your knowledge on recursion and pointer manipulation!

Checking Out The Code

As usual, copy lab_avl.zip into the remote servers.

Read the .h file

Before proceeding with the implementation, read the avltree.h file to understand what helper functions are available for the AVLTree class that we are working with today. This lab will be much more difficult if you do not do this! There is also a provided avltree_given.cpp that contains some boilerplate implementation. You do not (and should not) modify it!

Implement the updateHeight() function

Complete the implementation of the updateHeight() function. This function updates a single node’s height (i.e. it is non-recursive). You will need to use this function in the later portions of the lab.

Implement the insert() function

Complete the recursive insert() function. Note that rebalance() (which you will implement later) is called at every subtree on the way up. This is not required, but makes for simpler code and does not affect asymptotic complexity.

Note: let the current subtree key be K. The insertion should ensure that nodes with key strictly less than K are assigned to the left subtree, whereas nodes with key greater than or equal to K are assigned to the right subtree.

Once you are done, you should be able to run ./testavl and see non-empty trees in the output. Next, we will work on making them balanced.

Implement the rotation functions

Complete the implementation of rotateLeft(), rotateRight(), rotateLeftRight(), and rotateRightLeft(). We have partially implemented rotateLeft() to get you started, but you will need to use updateHeight() to update the heights for the rotate nodes.

If you need a refresher of what each rotation entails, check out the left rotation diagram Links to an external site. and right left rotation diagram Links to an external site..

Implement the rebalance() function

Complete the implementation of the 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. The cases are provided in written form, but you will need to convert these cases into code.

OPTIONAL - Implement the remove() function

Complete the implementation of the remove() function. You will only need to implement the case where a node with two children is removed from the tree. For testing purposes, use the predecessor when deleting the node. Refer to the lecture notes for more details on how to remove nodes from a BST/AVL tree.

Testing Your Code

To test your code, compile using make:

make

For a visual test, 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

The colored output for this lab can be confusing: you can look run ./testavl without color to see your true output, and compare it manually with soln_testavl.out.

If you haven't implemented insert() yet, then the output will all be (empty) trees.

If you haven’t implemented rebalance() or remove() yet, the tests will look strange. You can use the following to supress some tests before running your code:

./testavl reduced

You may also diff your solution with our expected output:

./testavl | diff -u - soln_testavl.out

You can run a second set of non-visual tests with:

./test

This second set tests all functions whose output is sent to standard output. If your code passes ./testavl, it should pass these as well.

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

Marking Your Work

As usual, we will grade your lab using a few tests in the autograder in PrarieLearn Links to an external site.. Submitting the lab is as simple as dragging your completed code into the PrarieLearn interface for the Lab AVL assignment.

Please submit the following file: avltree.cpp

Good luck!