Implementing Rotations

An unbalanced tree becomes balanced by performing an appropriate rotation operation. Section, Rebalancing Trees, illustrated how to perform rotations at a node. The code below gives the algorithm for the LL rotation, as illustrated in Figure below.

1 balanceLL(TreeNode A, TreeNode parentOfA) {
2 Let B be the left child of A.
3
4 if (A is the root)
5 Let B be the new root
6 else {
7 if (A is a left child of parentOfA)
8 Let B be a left child of parentOfA;
9 else
10 Let B be a right child of parentOfA;
11 }
12
13 Make T2 the left subtree of A by assigning B.right to A.left;
14 Make A the right child of B by assigning A to B.right;
15 Update the height of node A and node B;
16 } // End of method

Note that the height of nodes A and B can be changed, but the heights of other nodes in the tree are not changed. You can implement the RR, LR, and RL rotations in a similar manner.