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:

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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.