Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Single Rotations

Figure gif (a) shows an AVL balanced tree. For example, the balance factor for node A is zero, since its left and right subtrees have the same height; and the balance factor of node B is +1, since its left subtree has height h+1 and its right subtree has height h.

   figure19243
Figure: Balancing an AVL tree with a single (LL) rotation.

Suppose we insert an item into tex2html_wrap_inline63952, the left subtree of A. The height of tex2html_wrap_inline63952 can either increase or remain the same. In this case we assume that it increases. Then, as shown in Figure gif (b), the resulting tree is no longer AVL balanced. Notice where the imbalance has been manifested--node A is balanced but node B is not.

Balance can be restored by reorganizing the two nodes A and B, and the three subtrees, tex2html_wrap_inline63952, tex2html_wrap_inline63968, and tex2html_wrap_inline63970, as shown in Figure gif (c). This is called an LL rotation  , because the first two edges in the insertion path from node B both go to the left.

There are three important properties of the LL rotation:

  1. The rotation does not destroy the data ordering property so the result is still a valid search tree. Subtree tex2html_wrap_inline63952 remains to the left of node A, subtree tex2html_wrap_inline63968 remains between nodes A and B, and subtree tex2html_wrap_inline63970 remains to the right of node B.
  2. After the rotation both A and B are AVL balanced. Both nodes A and B end up with zero balance factors.
  3. After the rotation, the tree has the same height it had originally. Inserting the item did not increase the overall height of the tree!
Notice, the LL rotation was called for because the root became unbalanced with a positive balance factor (i.e., its left subtree was too high) and the left subtree of the root also had a positive balance factor.

Not surprisingly, the left-right mirror image of the LL rotation is called an RR rotation  . An RR rotation is called for when the root becomes unbalanced with a negative balance factor (i.e., its right subtree is too high) and the right subtree of the root also has a negative balance factor.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.