As was hopefully made clear in class, the performance of sorted binary trees is highly dependent upon whether or not they are “balanced”. A tree is said to be “balanced” if, for all nodes in the tree, the heights of the left and right subtrees do not differ by more than one. The height of a subtree is the number of nodes on the longest root to leaf path. If a tree is not balanced, the situation can be improved by performing “rotations” at selected nodes. One of the two basic rotations is called an “LL rotation”. The diagram below illustrates the effect of an LL rotation at node A. The triangles represent (possibly empty) subtrees. Note that these subtrees are not modified, but are simply moved around. Performing a rotation only involves modifying a handful of pointers.

An RR rotation is analogous to an LL rotation, but is the other way around.

In order to perform an LL rotation at a node, the node must have a left child, and in order to perform an RR rotation, the selected node must have a right child. Note that both kinds of rotations do not affect the sorting of a tree. If a tree is sorted before a rotation, it will still be sorted afterwards.

You have been supplied with a fully functional tree class (skeleton.h and skeleton.cpp) and a suitable test program (Treetest.cpp). The test program uses three class methods which been removed from the code supplied to you, though the prototypes still appear in the class header. These methods are:

// performs an LL rotation at the node containing the specified
// data value. Returns true if the rotation was successfully
// performed and false otherwise (not in tree or no left child)
bool rotateLL (int data);

// performs an RR rotation at the node containing the specified
// data value. Returns true if the rotation was successfully
// performed and false otherwise (not in tree or no right child)
bool rotateRR (int data);

// returns the height of the tree and sets "isBalanced" to true or
// false depending upon whether tree is balanced.
int height (bool &isBalanced);


Rename skeleton.h and skeleton.cpp to Tree.h and Tree.cpp and add the missing methods. Once you have your rotation methods working, experiment with rotations. Try, for example, inserting 12, 15, and 20 into an empty tree. Display the result. Then perform an RR at node 12 and display the modified tree. While we are a long way from fully implementing a self-balancing tree, we have obviously come up with a useful tool. In a proper AVL tree, rotations are performed as part of the insertion process, and the tree is kept balanced at all times. Sadly, however, the code required is a little too complex for a one-week assignment.

The height method should be a breeze. (Hint: Have a look at exercise #5 at the end of Chapter 13.) Remember that recursion can produce very simple answers to apparently complex problems!

Submit files Tree.h and Tree.cpp as your solution.

Updated: Tuesday, March 3rd, 2009.