Introduction To AVL Trees  
Dr. Thomas E. Hicks
Trinity University
[Set all IE margins to .5]

  ---------------- Double Rotate Right  ---------------- 

 


Double Rotate-Right Rotation (a) 
Example 1: Add Nodes 50, 10 (Balance Factors are Red!)
                                                  ________
                                                  |__50__| +1
                                          .
                        ________
                        |__10__| +0


Add Node 30

                                                  ________
                                                  |__50__| +2  <-- A
                                          .
                        ________
                        |__10__| -1  <-- B
                                   .
                                    ________
                                    |__30__| +0  <-- C/N 


Theory - Double Rotate-Right Rotation Needed (a)
  1. A is placed to the right of  C
  2. B  is placed to the left of  C
  3. Adjust Root/Father
                                                  ________
                                                  |__30__| +0  <-- C
                                          .                     .
                        ________                                            ________
                        |__10__| +0  <-- B                                  |__50__| +0  <--A

This is the simple/trivial case for Double  Rotate-Right Rotation (N is a leaf node with no sons). After the Double Rotate-Right Rotation
The Balance Factor of  A = ____________
The Balance Factor of  B = ____________
The Balance Factor of  C = ____________


AVL DOUBLE ROTATE - RIGHT Rotation (General Form A)  
Balanced subtree                                .    ?     .
(Prior To Insertion which forces a rotation):    .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+1_|_._| 
                                       .
               ______________________
               |_.__|___B__|_+0_|_._|



Un-Balanced subtree                             .    ?     .
(After Insertion - now needs a rotation):        .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+2_|_._|
                                       .
               ______________________
               |_.__|___B__|_-1_|_._|
                                      .
                                        ______________________
                                        |_.__|___C__|_+0_|_._|


Re-Balanced subtree                             .    ?     .
(After Double Rotate-Right(a) Rotation):         .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___C__|_+0_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                           ______________________          h+1 .
               |_.__|___B__|_+0_|_._|                           |_.__|___A__|_+0_|_._|              .



Add Node 20, 5 - No Rotation Needed               ________
                                                  |__30__| +1  <-- C
                                          .                     .
                        ________                                            ________
                        |__10__| +0  <-- B                                  |__50__| +0  <--A
                     .            .
           ________                   ________
           |___5__| +0                |__20__| +0 <-- N 
 


Add Node 25 - Rotation Needed                     ________
                                                  |__30__| +2  <-- A
                                          .                     .
                        ________                                            ________
                        |__10__| -1  <-- B                                  |__50__| +0
                     .            .
           ________                   ________
           |___5__| +0                |__20__| -1 <--C 
                                                                     .
                                               ________
                                               |__25__| +0  <-- N/C-R 


Theory - Double Rotate-Right Rotation Needed (b)
  1. A is placed to the right of  C
  2. B  is placed to the left of  C
  3. That which is to the right of C (C-R) is placed to the left of A
  4. That which is to the left of C (C-L) is placed to the right of B
  5. That which is to the left of B (B-L) stays to the left of B
  6. That which is to the right of A (A-R) stays to the right of A
  7. Adjust Root/Father
                                                  ________
                                                  |__20__| +0  <-- C
                                          .                     .
                        ________                                            ________
                        |__10__| +1  <-- B                                  |__30__| +0  <--A
                     .            .                                    .             .
           ________                                           ________                      ________
           |___5__| +0  <-- B-L                               |__25__| -0 <--C-R     |__50__| +0 <--A-R
 
This is the general case for Rotate-Right Rotation (N is a leaf node with no sons). After the Rotate-Right Rotation
The Balance Factor of  A = ___________________
The Balance Factor of  B = ___________________
The Balance Factor of  C = ___________________


Let us Add Node 12 Instead of Node 25  (above)- Rotation Needed
                                                  ________
                                                  |__30__| +2  <-- A
                                          .                     .
                        ________                                            ________
                        |__10__| -1  <-- B                                  |__50__| +0
                     .            .
           ________                   ________
           |___5__| +0                |__20__| +1 <--C 
                                                        .
                                ________
                                |__12__| +0  <-- N/C-L 

Theory - Double Rotate-Right Rotation Needed (c)
  1. A is placed to the right of  C
  2. B  is placed to the left of  C
  3. That which is to the right of C (C-R) is placed to the left of A
  4. That which is to the left of C (C-L) is placed to the right of B
  5. That which is to the left of B (B-L) stays to the left of B
  6. That which is to the right of A (A-R) stays to the right of A
  7. Adjust Root/Father
                                                  ________
                                                  |__20__| +0  <-- C
                                          .                     .
                        ________                                            ________
                        |__10__| +0  <-- B                                  |__30__| -1  <--A
                     .            .                                                 .
           ________                ________                                                           ________
           |___5__| +0  <-- B-L    |__12__| -0 <--C-L                                          |__50__| +0 <--A-R
 
This is the general case for Rotate-Right Rotation (N is a leaf node with no sons). After the Rotate-Right Rotation
The Balance Factor of  A = ___________________
The Balance Factor of  B = ___________________
The Balance Factor of  C = ___________________
   

AVL DOUBLE ROTATE - RIGHT Rotation (General Form B)  

Remember that when using AVL Rotations for Insertion, There will only be four standard forms which trigger rotations. The Double Rotate-Right rotation must occur whenever A = +2 and B = -1.
 

Balanced subtree                                .    ?     .
(Prior To Insertion which forces a rotation):    .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+1_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                                                            h+1.
               |_.__|___B__|_+0_|_._|                                           .                   .
              .                       .                                      __________________<..  .
            .                           .                                    |       A-R      |  .  .
 __________________<..                   ______________________              |                |  .  .
 |      B-L        | .                   |_.__|___C__|_+0_|_._|              |                |  .  .
 |                 | .                .                       .              |                |  .  .
 |                 | .   __________________<..       ..>__________________   |                |  .h .
 |                 | .   |       C-L      |  .       .  |       C-R      |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .  h-1  .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |________________|<..  .
 |                 | .   |                |  .       .  |                |                          .
 |_________________|<...>|________________|<..       .  |________________|<......................................
 



 Un-Balanced subtree                             .    ?     .
(After Insertion - now needs a rotation):        .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+2_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                                                               .
               |_.__|___B__|_-1_|_._|                                           .                   .
              .                       .                                      __________________<..  .
            .                           .                                    |       A-R      |  .  .
 __________________<..                   ______________________              |                |  .  .
 |      B-L        | .                   |_.__|___C__|_-1_|_._|              |                |  .  .
 |                 | .                .                       .              |                |  .  .
 |                 | .   __________________<..       ..>__________________   |                |  .h .
 |                 | .   |       C-L      |  .       .  |       C-R      |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .h-1   h.  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |________________|<..  .
 |                 | .   |                |  .       .  |                |                          .
 |_________________|<...>|________________|<..       .  |________________|                       h+2.
                                                     ..>|______N_________| <.....................................
 
  1.  A is placed to the right of  C
  2. B  is placed to the left of  C
  3. That which is to the right of C (C-R) is placed to the left of A
  4. That which is to the left of C (C-L) is placed to the right of B
  5. That which is to the left of B (B-L) stays to the left of B
  6. That which is to the right of A (A-R) stays to the right of A
  7. Adjust Root/Father


Re-Balanced subtree                             .    ?     .
(After Double Rotate-Right(b) Rotation):         .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___C__|_+0_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                           ______________________          h+1 .
               |_.__|___B__|_+1_|_._|                           |_.__|___A__|_+0_|_._|              .
               .                   .                             .                  .               .
            .                       .                           .                    .              .
 __________________<..   __________________<..       ..>__________________   __________________<..  .
 |      B-L        | .   |       C-L      |  .       .  |       C-R      |   |       A-R      |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .h-1    .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .h .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .   |________________|<..      h.  |________________|   |                |  .  .
 |_________________|<                                ..>|______N_________|   |________________|  .  .
 
 

AVL DOUBLE ROTATE - RIGHT Rotation (General Form C)  
Balanced subtree                                .    ?     .
(Prior To Insertion which forces a rotation):    .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+1_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                                                               .
               |_.__|___B__|_+0_|_._|                                           .                   .
              .                       .                                      __________________<..  .
            .                           .                                    |       A-R      |  .  .
 __________________<..                   ______________________              |                |  .  .
 |      B-L        | .                   |_.__|___C__|_+0_|_._|              |                |  .  .
 |                 | .                .                       .              |                |  .  .
 |                 | .   __________________<..       ..>__________________   |                |  .h .
 |                 | .   |       C-L      |  .       .  |       C-R      |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .  h-1  .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |________________|<..  .
 |                 | .   |                |  .       .  |                |                       h+1.
 |_________________|<...>|________________|<..       .  |________________|<......................................
 


Un-Balanced subtree                             .    ?     .
(After Insertion - now needs a rotation):        .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___A__|_+2_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                      h+2.
               ______________________                                                               .
               |_.__|___B__|_-1_|_._|                                           .                   .
              .                       .                                      __________________<..  .
            .                           .                                    |       A-R      |  .  .
 __________________<..                   ______________________              |                |  .  .
 |      B-L        | .                   |_.__|___C__|_+1_|_._|              |                |  .  .
 |                 | .                .                       .              |                |  .  .
 |                 | .   __________________<..       ..>__________________   |                |  .h .
 |                 | .   |       C-L      |  .       .  |       C-R      |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .h   h-1.  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |________________|<..  .
 |                 | .   |                |  .       .  |                |                          .
 |_________________|<.   |________________|  .       .  |________________|                          .
                      ..>|______N_________|<...................................................................................
 
 


Re-Balanced subtree                             .    ?     .
(After Double Rotate-Right(c) Rotation):         .        .
                                           __L__._Info_._bf_._R__  
                                           |_.__|___C__|_+0_|_._|<...................................
                                          .                          .                              .
                                      .                                   .                         .
               ______________________                           ______________________          h+1 .
               |_.__|___B__|_+0_|_._|                           |_.__|___A__|_-1_|_._|              .
               .                   .                             .                  .               .
            .                       .                           .                    .              .
  __________________<.   __________________<..       ..>__________________   __________________<..  .
 |      B-L        | .   |       C-L      |  .       .  |       C-R      |   |       A-R      |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .h  |                |  .    h-1.  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .h .
 |                 | .   |                |  .h      .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .   |                |  .       .  |                |   |                |  .  .
 |                 | .   |________________|  .       .  |________________|   |                |  .  .
 |_________________|<.   |______N_________|<..                               |________________|  .  .
 

In The Space Below, ADD  14, 16, 17, 18, & 19 to the tree above [practice additional ROTATE - LEFT rotations] Sketch!
 Label A, B, and N/C. Write in the balance factors.