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

  ---------------- Rotate Left ---------------- 
Example 2: Add Nodes 40, 50                                 ________
                                                  |__40__| -1
                                                                 .
                                                                        ________
                                                                        |__50__| +0
Add Node 60                                       ________
                                                  |__40__| -2  <-- A
                                                                  .
                                                                        ________
                                                                        |__50__| -1   <-- B
                                                                                     .
                                                                                     ________
                                                                                     |__60__| +0  <-- N 
Theory - Rotate-Left Rotation Needed (a)
  1. That which is to the right of B (B-R) stays to the right of  B
  2. A is placed to the left of B
  3. Adjust Root/Father
                                                  ________
                                                  |__50__| +0  <-- B
                                          .                     .
                        ________                                             ________
                        |__40__| +0  <-- A                                   |__60__| +0  <-- B-R

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 65 - No Rotation Needed                  ________
                                                  |__50__| -1 
                                           .                     .
                        ________                                             ________
                        |__40__| +0                                          |__60__| -1
                                                                                      .
                                                                                      ________
                                                                                      |__65__| +0 <-- N 
 

Add Node 70                                       ________
                                                  |__50__| -1 ?? <-- Father of A  
                                             .                     .
                        ________                                             ________
                        |__40__| +0                                          |__60__| -2 <-- A
                                                                                     .
                                                                                      ________
                                                                                      |__65__| -1 <-- B 
                                                                                                                                          .
                                                                                             ________
                                                                                             |__70__| +0  <-- N

Theory - Rotate-Left Rotation Needed (b)
A is placed to the left of B
                                                  ________
                                                  |__50__| -1   
                                          .                     .
                        ________                                             ________
                        |__40__| +0                                          |__65__| +0 <-- B
                                                                         .            .
                                                                  ________           ________
                                                                  |__60__| +0 <-A    |__70__| +0  <-- B-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  N = ___________________
The Balance Factor of Father of A = ____________
Add Node 71                                       ________
                                                  |__50__| -2  <-- A  
                                         .                     .
                        ________                                             ________
                        |__40__| +0                                          |__65__| -1  <-- B
                                                                         .            .
                                                                  ________           ________
                                                                  |__60__| +0        |__70__| -1  
                                                                                             .
                                                                                          ________
                                                                                          |__71__| +0  <-- N
Theory - Rotate-Left Rotation Needed (b)

 
 

A is placed to the left of B
                                                    ________
                                                    |__65__| +0  <-- B  
                                          .                     .
                        ________                                             ________
                        |__50__| +0  <-- A                                   |__70__| -1  <-- B-R
                     .           .                                                   .              
          ________                 ________                                            ________
          |__40__| +0  <-- A-L     |__60__| +0 <-- B-L                                 |__71__| +0
AVL ROTATE - LEFT Rotation (General Form)  

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

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

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

 

 

 

 

 

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

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