Chapter 26.5, Problem 26.5.1CP

RR rotation: In this type of rotation, the tree moves one position to right from the present position.

By using the Listing 26.2 as a template the algorithm for RR rotation is as follows:

Algorithm:

balanceRR (TreeNode A, TreeNode parentOfA)

{

Let B be the right child of A.

if (A is the root)

{

Let B be the new root

}

else

{

if(A is the left child of parentOfA)

Let B be the left child of parentOfA;

else

Let B be the right child of parentOfA;

}

Make T2 as the right subtree of A by assigning B.left to A.right;

Make A as the left child of B;

Update the height of node A and node B;

}

LR rotation: It is called as Left Right rotation. The tree performs a single left rotation that is followed by a single right rotation.

By using the Listing 26.2 as a template the algorithm for LR rotation is as follows:

Algorithm:

balanceLR (TreeNode A, TreeNode parentOfA)

{

Let B be the left child of A.

Let C be the right child of B.

if (A is the root)

{

Let C be the new root

}

else

{

if(A is the left child of parentOfA)

Let C be the left child of parentOfA;

else

Let C be the right child of parentOfA;

}

Make T3 as the left subtree of A by assigning C...