Computer Science 210

Data Structures

Fall 2018, Siena College

In this week's lab, you will experiment further with some of the tree structures we have been working with. In particular, AVL trees and heaps.

You will be assigned a partner to work with on this lab. Only one submission per group is needed.

As you finish each step, please have your instructor initial the hard copy of this lab handout you were issued to indicate successful completion.

Names: __ __

Learning goals:

- To gain a deeper understanding of AVL tree behavior by using an interactive visualization tool.
- To learn how AVL trees handle removal of values.
- To gain a deeper understanding of heap behavior by using an interactive visualization tool.
- To review some basic properties of heaps.

Submitting

Once all written items are initialed to indicate completion, turn in the hard copy of this lab handout you were issued.

Visualizing AVL Trees

We worked through some AVL tree examples in class, and you will be doing more of those as you complete the last problem set and again on the final exam. Our goal here is to gain a better understanding of AVL tree behavior by using an interactive algorithm visualization tool. The one we'll be using is called Visualgo, developed by Dr. Steven Halim and his collaborators.

Point your browser at
`https://visualgo.net/bn/bst`
to get to Visualgo's Binary Search Tree visualizations. Be sure to
click on "AVL TREE" at the top of the page to get AVL tree
behavior. Note that the controls at the bottom of the page allow you
to control the speed of the animation, and move forward or backward
through it.

Your first task is to build the AVL tree from the class example. The blue tab at the lower left brings up a menu of AVL tree operations. Use these controls to create an empty tree, then add these values in this order:

3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9

(you will need to do this in three "Insert" operations to stay within the system's limits for adding at once)

Watch carefully as the tree is built, and notice how Visualgo treats the double rotations as a pair of single rotations, but that the result is the same. Check that the results match those in the class example.

Using this tree as a starting point, come up with a series of insertions that demonstrate an additional example of each of the four cases we encountered that require rotations to restore balance. Please demonstrate each before moving on to the next.

Next, let's look at how AVL trees remain balanced following a remove operation.

Construct an example of an AVL tree in Visualgo and remove a value so that the remove results in a rotation to restore the AVL condition.

Construct an AVL tree with at least 10 values. Remove the root.

Heap Visualizations

Next, go to the Visualgo home page (click on the logo in the upper left) and choose the "Binary Heap" visualization.

Experiment with the visualization by building a heap with at least 12 values and extracting a few of them.

Recall that these kinds of heaps are normally stored using an array-based representation of trees.

Those formulas do not work when using Visualgo's scheme for numbering the tree nodes because they start with the root at index 1 instead of index 0.

Starting with a heap with at least 10 values, insert a value that will become the new root of the heap.