CS 112 Lab 7.   A game: balance BST with smallest number of rotations.

Agenda

Unbalanced nodes in a BST

In today's lab, we will see balancing a Binary Search Tree (BST) using rotations. Recall that a node in a tree is unbalanced if the difference in heights of its left and right subtrees is > 1. In the example below, nodes shaded gray are unbalanced nodes and nodes shaded orange are balanced nodes.


Overview of rotations used to balance a BST



With respect to hinge node N: L is leftChild, LL is leftLeftChild, R is right child, RR is rightRightChild.

Example using rotations to balance a BST

Today's example and associated tasks

Download class files for the lab below,

  • BinaryTreeNode.java

    rotateCounterClockwise() and rotateClockwise() are mirror methods. We provide implementaition of rotateCounterClockwise() in BinaryTreeNode. The only method to change in this class is rotateClockwise(). Currently this method contains the exact same code as rotateCounterClockwise.

    Task: Modify rotateClockwise() following comments to mirror the operation of rotateCounterClockwise().

  • DisplayWindow.java

    This is the client driver class to test our BST rotations. Nothing to change in this class.

    Follow instructions in graphics window to play the game.

Solutions

BinaryTreeNode.java

DisplayWindow.java

URL

http://cs-people.bu.edu/tvashwin/cs112_spring08/lab07.html