Learning Objectives
- Implement tree balancing manipulations.
- Modify a known function (insert) to accomplish a more complex task
Submission Instructions
Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).
You will only need to modify the following files:
lab_avl.ipynb
Assignment Description
The AVL tree (named after its two inventors Adelson-Velsky and Landis) is a self-balancing binary tree. As you have seen many times by now, trees are very useful data structures but only if their height is closer to the optimal O(log n) than the worst case O(n). Accordingly, by balancing a tree when necessary, we can achieve a guaranteed O(log n) runtime for most operations. Trees optimized in this way can be used to implement other data structures such as sets and maps. They are also a useful data structure to have in our toolkits for a lot of problems and a core component in many algorithms.
Here you will be implementing some basic functionalities on the AVL tree – all the rotations as well as the rebalance function that modifies BST insert and remove. Given the large degree of similarity between an AVL tree and a BST, you are strongly encouraged to compare both the code and the outcome of inserting between lab_bst and lab_avl.
Part 1: AVL Rotations
AVL trees are balanced using one of four different rotations depending on the context. Let’s implement them one by one to understand how each works. To keep things simple, these rotations are outside of the avl() class and each have the same input / output:
# INPUT:
# A treeNode object where there is an inbalance
# OUTPUT:
# A balanced treeNode object
# NOTE: rotate returns the 'new' root node of the subtree
# Accordingly, it is used by 'node = rotate(node)'
treeNode rotate(treeNode node)
For full credit here, you must implement:
- rotateRight
- rotateLeft
- rotateRightLeft
- rotateLeftRight
NOTE: There are a number of useful resources for picturing AVL rotations. Included here:
HINT: You may find rotateRight and rotateLeft useful when writing rotateRightLeft and rotateLeftRight.
Part 2: AVL Rebalancing
As covered in class, AVL insertion is largely the same as BST insertion (and has been provided for you in the code). However in order to properly insert into an AVL tree, you have to implement the rebalance function.
# INPUT:
# A treeNode object which is the root of the current sub-tree
# OUTPUT:
# a treeNode that defines the root of the current sub-tree
# Rebalance should check for balance and -- if necessary -- perform the correct rotation
# NOTE: If the tree is balanced, rebalance should return the input node unchanged.
treeNode rebalance(treeNode node):
Here ‘rebalance’ is a bit of a misnamed function as it first checks to see if there is an inbalance in the tree at a particular node. If the tree is balanced, the function should return the node unchanged (you do not rebalance a balanced node). If there is an inbalance detected, rebalance should then call the appropriate rotation and return the new root node of the rebalanced sub-tree. It is up to you to determine which of the four rotations should be called for any given input as well as how to use the previously implemented rotation functions in this context.
NOTE: You should use all four previously implemented rotations in this function. Look back at the notes if you are unsure when to call a particular rotation.
HINT: You should look at utils.py (or the top import line) to see what functions have been provided for you. Some of them may be relevant to checking the balance of any particular node.