Lab 10 -- More Trees

Lab 10: More Trees
Due: 4:00 PM, Friday, December 7, 2018

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.

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

Question 1: State the AVL balance condition. (2 points)

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:

(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.

Question 2: Demonstrate that your final tree in Visualgo has been created properly. (5 points)

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.

Question 3: State Case 1 and demonstrate your Case 1 visualization. (8 points)

Question 4: State Case 2 and demonstrate your Case 2 visualization. (8 points)

Question 5: State Case 3 and demonstrate your Case 3 visualization. (8 points)

Question 6: State Case 4 and demonstrate your Case 4 visualization. (8 points)

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.

Question 7: Demonstrate your example of a remove that results in a rotation. (10 points)

Question 8: Describe how the tree chooses a value to become the new root. (5 points)

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.

Question 9: Is Visualgo using a min heap or a max heap? (2 points)

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

Question 10: For the heap you built above, draw its array representation. (3 points)

Question 11: In class, we learned the formulas for finding the array indices that contain a value at index i's parent and children. What are the formulas to find the parent, left child, and right child? (3 points)

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.

Question 12: What are the formulas to find the array indices that contain the parent, left child, and right child when the root is at index 1? (3 points)

Question 13: Explain briefly why there is no option to insert a value at a particular location in the heap. That is, why is the only parameter to Insert the value you wish to insert? (5 points)

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

Question 14: Demonstrate your example of an Insert that causes the new value to become the root of the heap. (5 points)

Question 15: Explain briefly why there is no option to remove an arbitrary value from the heap. That is, why is the only way to remove a value from the heap via the ExtractMax method? (5 points)

Question 16: If you have a heap with 50 values, what is the largest number of comparisons that it will need to make to restore the heap condition after adding a new value? Under what circumstances will that occur? Explain briefly. (5 points)

Question 17: If you have a heap with 50 values, what is the fewest number of comparisons that it will need to make to restore the heap condition after adding a new value? Under what circumstances will that occur? Explain briefly. (5 points)

Question 18: If you have a heap with 50 values, what is the largest number of comparisons that it will need to make to restore the heap condition after removing a value? Under what circumstances will that occur? Explain briefly. (5 points)

Question 19: If you have a heap with 50 values, what is the fewest number of comparisons that it will need to make to restore the heap condition after removing a value? Under what circumstances will that occur? Explain briefly. (5 points)