lab_avl

Ageless AVL

Due: Nov 04, 23:59 PM

Learning Objectives

  • Implement tree balancing manipulations.
  • Modify a known function (insert) to accomplish a more complex task

Reminder: You can fill out an optional survey on Moodle after each lab!

Setup

From your CS 277 git directory, run the following:

git fetch release
git merge --allow-unrelated-histories release/lab_avl -m "Merging initial lab_avl files"

Upon a successful merge, your lab_avl files are now in your lab_avl directory.

Assignment Description

The AVL tree (named after its two inventors Adelson-Velsky and Landis) is a self-balancing binary tree. 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.

Here you will be implementing some basic functionalities on the AVL tree – all the rotations as well as insertion. 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 is simultaneously implementing two parts of the AVL tree. The first step of the rebalance function is to actually check the balance of the input node. If the tree is balanced, the function should return the node unchanged (you do not rebalance a balanced node). If, however, there is an inbalance detected rebalance should call the appropriate rotation and return the new root node of the rebalanced sub-tree.

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.