Section 4 - Implementing Rotation

5A.4.1 Single Rotation

It is with mixed emotions that I provide you with, or refer you to, code that does rotations. Writing and debugging this kind of code is what turns you into strong, capable programmers. On the other hand, I know that you don't have unlimited time, and cannot write all the functions on your own. So I've decided to give you the code here, with the understanding that you will compare it scrupulously with the rules and pictures that came before and make sure you agree that it does what it should. Also, I'll give you a chance to do some implementation coding in your homework assignment.

The pictures and rules are in the previous pages, and I have kept the names like k₁ and k₂ as before, using k₂ as the center of a single rotation, and k₁ as its left or right child. As usual, I am giving you an implementation which presumes the template prototype is declared, above. I have not yet shown you that prototype, because there are some other things to say before I reveal the big picture.

Single Left Rotation

template <class Comparable>
void FHavlTree<Comparable>::rotateWithLeftChild( FHs_treeNode<Comparable> * & k2 )
{
   FHs_treeNode<Comparable> *k1 = k2->lftChild;
   k2->lftChild = k1->rtChild;
   k1->rtChild = k2;
   k2->setHeight( max( heightOf(k2->lftChild),  heightOf(k2->rtChild) ) + 1 );
   k1->setHeight( max( heightOf(k1->lftChild),  k2->getHeight() ) + 1 );
   k2 = k1;
}

Anomalies to ignore for now:

• The parameter k2 and the local variable k1 are FHs_treeNode*s, our general search tree node type, not AvlNode*s. We will see why, later.
• I am using accessors and mutators to reference the height member rather than just saying k1->height. There is a reason for that, too, but the effect for us now is the same. It is needed, otherwise, I would not waste the function call.

Things to observe:

• There is a private static method max() which returns the maximum of two ints. You'll see it eventually, but it is a one-liner that looks exactly as you would expect.
• The way we set the height of a node after we have moved some links around is standard procedure: take the max height of its two new children and add 1.
• Like many methods we have seen, we are passing a pointer, k2, but we are passing it by reference. This is so that when we use a line like k2 = k1 (the finale of this method), the assignment is reflected in the client.

Single Right Rotation

Here is the companion method:

template <class Comparable>
void FHavlTree<Comparable>::rotateWithRightChild( FHs_treeNode<Comparable> * & k2 )
{
   FHs_treeNode<Comparable> *k1 = k2->rtChild;
   k2->rtChild = k1->lftChild;
   k1->lftChild = k2;
   k2->setHeight( max( heightOf(k2->lftChild), heightOf(k2->rtChild) ) + 1 );
   k1->setHeight( max( heightOf(k1->rtChild), k2->getHeight() ) + 1 );
   k2 = k1;
}

5A.4.2 Double Rotation

Because double rotation was simply the composition of two single rotations, the coding for this esoteric maneuver is dramatically simple:

template <class Comparable>
void FHavlTree<Comparable>::doubleWithLeftChild( FHs_treeNode<Comparable> * & k3 )
{
   rotateWithRightChild(k3->lftChild);
   rotateWithLeftChild(k3);
}

Hidden in the streamlined logic is the fact that k2, the center of the first of the two rotations, does not have to be named, explicitly -- it is, after all, just k3->lftChild. The association with k2 comes by looking at the formal parameter name in rotateWithRightChild().

Here is the companion:

template <class Comparable>
void FHavlTree<Comparable>::doubleWithRightChild( FHs_treeNode<Comparable> * & k3 )
{
   rotateWithLeftChild(k3->rtChild);
   rotateWithRightChild(k3);
}

The coding for these methods is deceptively simple. It belies the careful design and debugging needed to go into the class as a whole, leading to the details in the bullets above. Why use FHs_treeNodes instead of AvlNodes? Why uses accessors for the public member height? You'll see the reasons, but it isn't quite the same as doing it yourself. That's why I want to encourage you to at least master the logic here, and when we get to the next phase of implementation, likewise, study every move, asking me if you have any questions.

You may even be able to find improvements to my code, which I would celebrate, with a fine bottle of Pinot AVL.