Lab 6

Today we will implement rotations that keep a tree balanced. You should create a directory called lab6 where you will save your work and gsubmit this directory when you are done with the lab.

Your job is to finish the implementation of BinaryTreeNode.java by coding a complementary rotation. Right now there are two methods Rotate and RotateAlternate that are exactly the same. You will need to change the implementation of RotateAlternate to handle the symmetric case. To test whether the new rotation is working you should run DisplayWindow.java, which will pop up an interactive window displaying a BST. In the graphical interface the nodes that are not balanced (a node is unbalanced if the heights of its left and right subtrees differ by more than 1) are displayed in gray, and you can left/right click to rotate nodes.

The changes you need to make to the code are very small, you should start by studying the implementation of the given rotation, and then change it symmetrically. Your TF will help you understand what is going on by drawing a picture on the board. You can think of the rotation that you need to implement as a counter-clockwise rotation, even though it implements a clockwise rotation in the graphical interface :) Don't worry about that, and just implement the symmetric case (what is clockwise has to do with how the coordinates of the graphical interface are set up).