AVL Tree: Height-Balanced Binary Search Tree Implementation With Examples

What is AVL tree?

AVL tree is the height balanced binary search tree. AVL tree is named after its inventors Adelson-Velskii and Landis. AVL tree is the first proposed dynamically balanced tree. In AVL tree the sub trees are balanced in height of at-most 1. The balance factor is computed using the below formula:

Balanced Factor=| Height of Left Sub tree – Height of the Right sub tree |

In AVL tree operation like insertion, deletion and searching time of the AVL tree is O(log n).

Thus, AVL tree is a binary search tree with the following two properties:

• In AVL tree, every sub tree is an AVL tree.
• All sub tree of the AVL tree differ in height by at-most 1

On inserting a node to the binary search tree, the tree may end up in unbalanced state with balance factor exceeding 1. In such situation it is check whether the left sub tree height is more, or right sub tree height is more. In right sub tree height is more it is rotated to left. If the left sub tree height is more it is rotated to right. In rotation there are four cases like LL (Left-Left) rotation, LR (Left-Right) rotation, RR (Right-Right) rotation, RL (Right-Left) rotation.

LL (Left Left) Rotation:

A                                                                  B                    

                                                                  /   

      B                                  à                  A      C

           C

In the above case the node A is in unbalanced state as new node is inserted as the right child to the right sub tree of A. So, a LL rotation is performed to bring the tree into the balanced state.

LR (Left Right) Rotation or Double Left Rotation:

     A                                                           C

    /                                                            /    

   B                                     à                 B     A

      C

In the above case the node A is in unbalanced state as new node is inserted as the right child to the left sub tree of A. So, a LR rotation is performed to bring the tree into the balanced state.

RR (Right Right) Rotation:

             A                                                      B

           /                                                        /   

         B                                à                   C     A

       /

     C      

In the above case the node A is in unbalanced state as new node is inserted as the left child to the left sub tree of A. So, a RR rotation is performed to bring the tree into the balanced state. 

RL (Right Left) Rotation or Double Right Rotation:

     A                                                                C

                                                                      /    

           B                             à                       A    B   

           /

          C

In the above case the node A is in unbalanced state as new node is inserted as the left child to the right sub tree of A. So, a rotation is performed to bring the tree into the balanced state.

Author Name:

Instructions to use the code:

The int isBalanced(BSTHead *mytree) is used to determine whether the tree is balanced, left skewed, or right skewed. This function is used whenever a new node is inserted or deleted from the binary search tree.

The void rotateLeft(Node *pPre) is used to rotate the tree unbalanced at  right to be rotated to left.

The void rotateRight(Node *pPre) is used to rotate the tree unbalanced at  left to be rotated to right.

References:

Drozdek, A. (2013). Data Structures and Algorithms in C++.  Boston,  MA: Cengage Learning.

Storer, J.A. (2002). An Introduction to Data Structures and Algorithms. Springer Science.

Weiss, M. A. (1996). Algorithms, Data Structures, and Problem Solving with C++. Addison-Wesley Publishing Company.

Weiss, M. A. (2014). Data Structures and Algorithm Analysis in C++. Pearson Education Limited.