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

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 10                                       ________
                                                  |__40__| +1 ?? <-- Father of A  
                                          .                      .
                        ________                                             ________
                        |__30__| +2  <-- A                                   |__50__| +0
                       .
              ________
              |__20__| +1  <-- B
             .
      ________
      |__10__| +0  <-- N

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

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

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_________|<...