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

  ---------------- Rotate Right  ---------------- 
Example 1: Add Nodes 50, 40 (Balance Factors are Red!)
                                                  ________
                                                  |__50__| +1
                                          .
                        ________
                        |__40__| +0

Add Node 30
                                                  ________

                                                  |__50__| +2  <-- A
                                          .
                        ________
                        |__40__| +1  <-- B
                       .
              ________
              |__30__| +0  <-- N 

Theory - Rotate-Right Rotation Needed (a)
  1. That which is to the left of B (B-L) stays to the left of B
  2. A is placed to the right of B
  3. Adjust Root/Father

                                                  ________
                                                  |__40__| +0  <-- B
                                          .                     .
                        ________                                             ________
                        |__30__| +0  <-- B-L                                 |__50__| +0  <--A

This is the simple/trivial 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  N = ____________


Add Node 20 - No Rotation Needed                  ________
                                                  |__40__| +1 
                                           .                     .
                        ________                                             ________
                        |__30__| +1                                          |__50__| +0
                       .
              ________
              |__20__| +0 <-- N 

  Add Node 10                                       ________
                                                  |__40__| +1 ?? <-- Father of A  
                                          .                      .
                        ________                                             ________
                        |__30__| +2  <-- A                                   |__50__| +0
                       .
              ________
              |__20__| +1  <-- B
             .
      ________
      |__10__| +0  <-- N


Theory - Rotate-Right Rotation Needed (b)
  1.  That which is to the right of B (B-R) is placed to the left of A
  2. That which is to the left of B (B-L) stays to the left of B
  3. That which is to the right of A (A-R) stays to the right of A
  4. A is placed to the right of B
    Adjust Root/Father
                                                  ________
                                                  |__40__| +1   
                                          .                     .
                        ________                                             ________
                        |__20__| +0  <-- B                                   |__50__| +0
                       .            .
              ________           ________
              |__10__| +0 <-B-L  |__30__| +0  <-- A
  
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  N = ___________________
The Balance Factor of Father of A = ____________

Add Node 9                                        ________
                                                  |__40__| +2  <-- A  
                                          .                     .
                        ________                                             ________
                        |__30__| +1  <-- B                                   |__50__| +0
                     .            .
              ________            ________
              |__10__| +1         |__30__| +0
                       .
      ________
      |___9__| +0  <-- N

Theory - Rotate-Right Rotation Needed (b)
  1.  That which is to the right of B (B-R) is placed to the left of A
  2. That which is to the left of B (B-L) stays to the left of B
  3. That which is to the right of A (A-R) stays to the right of A
  4. A is placed to the right of B
  5. Adjust Root/Father

                                                  ________
                                                  |__20__| +0  <-- B  
                                          .                     .
                        ________                                             ________
                        |__10__| +1  <-- B-L                                 |__40__| +0  <-- A
                     .           .                                        .          .              
              ________                                           ________             ________
              |___9__| +0                                        |__30__| +0 <-- B-R  |__50__| +0 <-- A-R


AVL ROTATE - RIGHT Rotation (General Form)  

Remember that when using AVL Rotations for Insertion, There will only be four standard forms which trigger rotations. The 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_|_._|<................................
                                          .                       .                              .
                                      .                               .                          .
               ______________________                                   __________________<..    .
               |_.__|___B__|_+0_|_._|<.........................         |       A-R      |  .    .
               .                    .                         .         |                |  .    .
  __________________<..          __________________<..        .         |                |  .h   .h+2
 |      B-L        |  .          |       B-R      |  .        .         |                |  .    .
 |                 |  .          |                |  .        .         |                |  .    .
 |                 |  .h         |                |  .h       .h+1      |                |  .    .
 |                 |  .          |                |  .        .         |________________|<..    .
 |                 |  .          |                |  .        .                                  .
 |_________________|<...........>|________________|<..............................................  
 

  1.  That which is to the right of B (B-R) is placed to the left of A
  2. That which is to the left of B (B-L) stays to the left of B
  3. That which is to the right of A (A-R) stays to the right of A
  4. A is placed to the right of B
  5. Adjust Root/Father

 

 

 

 

 

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



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