There are four types of four AVL rotations:

1. Single Right Rotation (SRR):

   A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the left (the left subtree is 2 higher than the right subtree) and B is left-heavy (the left subtree of B is 1 higher than the right subtree of B). T1, T2 and T3 represent subtrees (a node was added to T1 which made B leftheavy and unbalanced A).

           A        SRR at A        B
          / \      ---------->     / \
         B  T3                    T1  A
        / \                          / \
       T1 T2                        T2 T3
     

2. Single Left Rotation (SLR):

   A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree) and B is right-heavy (the right subtree of B is 1 higher than the left subtree of B). T1, T2 and T3 represent subtrees (a node was added to T3 which made B right-heavy and unbalanced A).

           A        SLR at A        B
          / \      ---------->     / \
         T1  B                    A  T3
            / \                  / \
           T2  T3               T1 T2
     

3. Double Left Rotation (DLR):

   C is the node that the rotation is performed on. This rotation is performed when C is unbalanced to the left (the left subtree is 2 higher than the right subtree), A is right-heavy (the right subtree of A is 1 higher than the left subtree of A) and B is left-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T2 which made B left-heavy, made A right-heavy and unbalanced C). This consists of a single left rotation at node A, followed by a single right at node C.

           C        SLR at A         C        SRR at C       B
          / \      ---------->     /   \     --------->    /   \
         A  T4                    B     T4                A     C
        / \                      / \                     / \   / \
       T1  B                    A   T3                  T1 T2 T3 T4
          / \                  / \
         T2 T3                T1 T2
     

   That is,

           DLR equiv SLR + SRR
     

4. Double Right Rotation (DRR):

   A is the node that the rotation is performed on. This rotation is performed when A is unbalanced to the right (the right subtree is 2 higher than the left subtree), C is leftheavy (the left subtree of C is 1 higher than the right subtree of C) and B is right-heavy. T1, T2, T3, and T4 represent subtrees (a node was added to T3 which made B right-heavy, made C left-heavy and unbalanced A). This consists of a single right at node C, followed by a single left at node A.

           A        SRR at C         A         SLR at A         B
          / \      ---------->     /   \      ---------->     /   \
         T1  C                    T1    B                    A     C
            / \                        / \                  / \   / \
           B  T4                      T2  C                T1 T2 T3 T4
          / \                            / \
         T2 T3                          T3 T4
     

   That is,

           DRR equiv SRR + SLR
   

   ---

   A C++ example of the AVL Tree Source Code is available here

Copyright © 1998 David Pearson. All rights reserved