CSci 2101 Lab 11.

This is a multi-day lab with several intermediate submissions. Work in groups of 2-4 on this lab.

AVL trees (50 points)

Part 1 is due Monday, April 24th at 11:59pm

Task 1

Your goal is to explore balanced binary search trees, and specifically AVL tree approach to tree balancing. In AVL trees the heights (i.e. the number of levels) of the left and the right subtree of every node differ by no more than 1. If a node just added to a binary search tree breaks that balance, a rotation is performed to fix the unbalance. There are 4 rotations, all are shown here.

Your task is to implement at least two rotations (one straight line, such as L-L or R-R), and the other one a zigzag (such as L-R or R-L). Some specific things to pay attention to:

• Assume that there are no duplicated keys in the tree.
• Start with the binary search tree code here (it has the put method and traversals methods that can be used for testing)
• First add heights to a node (you can store its own height or the heights of its left and right subtree). You might want to write a method that, given a key, returns the height of that node. This is helpful for testing. Try just adding elments and keep track of the heights.
• As you start implementing rotations, note that you need to correct the lowest unbalanced node on the way to the node that you've just added.
• Also note that the balance is corrected at the parent of the node that is unbalanced.
• First implement re-balancing a regular node, test it (use the traversals to print the tree: in-order and pre-order traversals combined give you the tree shape).
• After you get this to work, implement re-balancing the root.
• Make sure that you reset the heights after re-balancing.
• Fixing the zigzag pattern may be implemented as two rotations (the way it is described in the wikipedia page) or at once. Either way is fine.
• Make sure that your rotations are efficient: they should not descend into subtrees that are not on the path to the newly added node.

Please submit your work-in-progress to me by 11:59pm on Monday.

Task 2

Give a brief (5-7 minutes) description of your approach (show the code) in the lab on Tuesday.

Task 3

You will get another group's code to check and comment on. Submit your findings to me by 11:59pm Friday April 28th.

How to submit

Submit the java file(s), including your testing code, by e-mail to me. The subject of the message must be 2101 Lab 11. Make sure to CC your group partner.

CSci 2101 course web site.