AVL Trees: Rotations, Insertion, Deletion with C++ Example

In this Algorithm tutorial, you will learn:

• What are AVL Trees?
• How does AVL Tree work?
• Balance Factor in AVL Trees
• Properties of Balance Factor
• AVL Rotations
• Left – Left Rotation
• Right – Right Rotation
• Right – Left Rotation
• Left – Right Rotation
• Insertion in AVL Trees
• Deletion in AVL Trees
• C++ Example of AVL Trees
• Advantages of AVL Trees

How does AVL Tree work?

To better understand the need for AVL trees, let us look at some disadvantages of simple binary search trees.

Consider the following keys inserted in the given order in the binary search tree.

The height of the tree grows linearly in size when we insert the keys in increasing order of their value. Thus, the search operation, at worst, takes O(n).

It takes linear time to search for an element; hence there is no use of using the Binary Search Tree structure. On the other hand, if the height of the tree is balanced, we get better searching time.

Let us now look at the same keys but inserted in a different order.

Here, the keys are the same, but since they are inserted in a different order, they take different positions, and the height of the tree remains balanced. Hence search will not take more than O(log n) for any element of the tree. It is now evident that if insertion is done correctly, the tree's height can be kept balanced.

In AVL trees, we keep a check on the height of the tree during insertion operation. Modifications are made to maintain the balanced height without violating the fundamental properties of Binary Search Tree.

Balance Factor in AVL Trees

Balance factor (BF) is a fundamental attribute of every node in AVL trees that helps to monitor the tree's height.

Properties of Balance Factor

• The balance factor is known as the difference between the height of the left subtree and the right subtree.
• Balance factor(node) = height(node->left) - height(node->right)
• Allowed values of BF are –1, 0, and +1.
• The value –1 indicates that the left sub-tree contains one extra, i.e., the tree is left heavy.
• The value +1 indicates that the left sub-tree contains one extra, i.e., the tree is left heavy.
• The value 0 shows that the tree includes equal nodes on each side, i.e., the tree is perfectly balanced.

AVL Rotations

To make the AVL Tree balance itself, when inserting or deleting a node from the tree, rotations are performed.

We perform the following LL rotation, RR rotation, LR rotation, and RL rotation.

• Left – Left Rotation
• Right – Right Rotation
• Right – Left Rotation
• Left – Right Rotation

Left – Left Rotation

This rotation is performed when a new node is inserted at the left child of the left subtree.

A single right rotation is performed. This type of rotation is identified when a node has a balanced factor as +2, and its left-child has a balance factor as +1.

Right – Right Rotation

This rotation is performed when a new node is inserted at the right child of the right subtree.

A single left rotation is performed. This type of rotation is identified when a node has a balanced factor as -2, and its right-child has a balance factor as -1.

Right – Left Rotation

This rotation is performed when a new node is inserted at the right child of the left subtree.

This rotation is performed when a node has a balance factor as –2, and its right-child has a balance factor as +1.

Left – Right Rotation

This rotation is performed when a new node is inserted at the right child of the left subtree.

This rotation is performed when a node has a balance factor as +2, and its right-child has a balance factor as -1.

Insertion in AVL Trees

Insert operation is almost the same as in simple binary search trees. After every insertion, we balance the height of the tree. Insert operation takes O(log n) worst time complexity.

Step 1:Insert the node in the AVL tree using the same insertion algorithm of BST. In the above example, insert 160.

Step 2:Once the node is added, the balance factor of each node is updated. After 160 is inserted, the balance factor of every node is updated.

Step 3:Now check if any node violates the range of the balance factor if the balance factor is violated, then perform rotations using the below case. In the above example, the balance factor of 350 is violated and case 1 becomes applicable there, we perform LL rotation and the tree is balanced again.

1. If BF(node) = +2 and BF(node -> left-child) = +1, perform LL rotation.
2. If BF(node) = -2 and BF(node -> right-child) = 1, perform RR rotation.
3. If BF(node) = -2 and BF(node -> right-child) = +1, perform RL rotation.
4. If BF(node) = +2 and BF(node -> left-child) = -1, perform LR rotation.

Deletion in AVL Trees

Deletion is also very straight forward. We delete using the same logic as in simple binary search trees. After deletion, we restructure the tree, if needed, to maintain its balanced height.

Step 1: Find the element in the tree.

Step 2: Delete the node, as per the BST Deletion.

Step 3: Two cases are possible:-

Case 1: Deleting from the right subtree.

• 1A. If BF(node) = +2 and BF(node -> left-child) = +1, perform LL rotation.
• 1B. If BF(node) = +2 and BF(node -> left-child) = -1, perform LR rotation.
• 1C. If BF(node) = +2 and BF(node -> left-child) = 0, perform LL rotation.

Case 2: Deleting from left subtree.

• 2A. If BF(node) = -2 and BF(node -> right-child) = -1, perform RR rotation.
• 2B. If BF(node) = -2 and BF(node -> right-child) = +1, perform RL rotation.
• 2C. If BF(node) = -2 and BF(node -> right-child) = 0, perform RR rotation.

C++ Example of AVL Trees

Below is the C++ code that implements AVL trees:

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct node {
    struct node *left;
    int data;
    int height;
    struct node *right;

};

class AVL
{
private:
    
public:
    struct node * root;
    AVL(){
        this->root = NULL;

    }

    int calheight(struct node *p){

            if(p->left && p->right){
            if (p->left->height < p->right->height)
                return p->right->height + 1;
            else return  p->left->height + 1;
            }
            else if(p->left && p->right == NULL){
               return p->left->height + 1;
            }
            else if(p->left ==NULL && p->right){
               return p->right->height + 1;
            }
            return 0;

    }

    int bf(struct node *n){
            if(n->left && n->right){
                return n->left->height - n->right->height; 
            }
            else if(n->left && n->right == NULL){
                return n->left->height; 
            }
            else if(n->left== NULL && n->right ){
                return -n->right->height;
            }
    }

    struct node * llrotation(struct node *n){
        struct node *p;
        struct node *tp;
        p = n;
        tp = p->left;

        p->left = tp->right;
        tp->right = p;

        return tp; 
    }


    struct node * rrrotation(struct node *n){
        struct node *p;
        struct node *tp;
        p = n;
        tp = p->right;

        p->right = tp->left;
        tp->left = p;

        return tp; 
    }


    struct node * rlrotation(struct node *n){
        struct node *p;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->right;
        tp2 =p->right->left;

        p -> right = tp2->left;
        tp ->left = tp2->right;
        tp2 ->left = p;
        tp2->right = tp; 
        
        return tp2; 
    }

    struct node * lrrotation(struct node *n){
        struct node *p;
        struct node *tp;
        struct node *tp2;
        p = n;
        tp = p->left;
        tp2 =p->left->right;

        p -> left = tp2->right;
        tp ->right = tp2->left;
        tp2 ->right = p;
        tp2->left = tp; 
        
        return tp2; 
    }

    struct node* insert(struct node *r,int data){
        
        if(r==NULL){
            struct node *n;
            n = new struct node;
            n->data = data;
            r = n;
            r->left = r->right = NULL;
            r->height = 1; 
            return r;             
        }
        else{
            if(data < r->data)
            r->left = insert(r->left,data);
            else
            r->right = insert(r->right,data);
        }

        r->height = calheight(r);

        if(bf(r)==2 && bf(r->left)==1){
            r = llrotation(r);
        }
        else if(bf(r)==-2 && bf(r->right)==-1){
            r = rrrotation(r);
        }
        else if(bf(r)==-2 && bf(r->right)==1){
            r = rlrotation(r);
        }
        else if(bf(r)==2 && bf(r->left)==-1){
            r = lrrotation(r);
        }        

        return r;

        }

    void levelorder_newline(){
        if (this->root == NULL){
            cout<<"\n"<<"Empty tree"<<"\n";
            return;            
        }
        levelorder_newline(this->root);
    }

    void levelorder_newline(struct node *v){
        queue <struct node *> q;
        struct node *cur;
        q.push(v);
        q.push(NULL);      

        while(!q.empty()){
            cur = q.front();
            q.pop();
            if(cur == NULL && q.size()!=0){
                cout<<"\n";
                
                q.push(NULL);
                continue;
            }
            if(cur!=NULL){
                cout<<" "<<cur->data;

                if (cur->left!=NULL){
                q.push(cur->left);
                }
                if (cur->right!=NULL){
                    q.push(cur->right);
                }
            }
            
            
        }
    }
 
    struct node * deleteNode(struct node *p,int data){

        if(p->left == NULL && p->right == NULL){
                if(p==this->root)
                    this->root = NULL;
            delete p;
            return NULL;
        }

        struct node *t;
        struct node *q;
        if(p->data < data){
            p->right = deleteNode(p->right,data);
        }
        else if(p->data > data){
            p->left = deleteNode(p->left,data);
        }
        else{
            if(p->left != NULL){
                q = inpre(p->left);
                p->data = q->data;
                p->left=deleteNode(p->left,q->data);
            }
            else{
                q = insuc(p->right);
                p->data = q->data;
                p->right = deleteNode(p->right,q->data);
            }
        }

        if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }                  
        else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
        else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
        else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }

        
        return p;
    }

     struct node* inpre(struct node* p){
        while(p->right!=NULL)
            p = p->right;
        return p;    
    }

    struct node* insuc(struct node* p){
        while(p->left!=NULL)
            p = p->left;

        return p;    
    }

    ~AVL(){

    }
};


int main(){

    AVL b;
    int c,x;

    do{
        cout<<"\n1.Display levelorder on newline";
        cout<<"\n2.Insert";
        cout<<"\n3.Delete\n";
        cout<<"\n0.Exit\n";
        cout<<"\nChoice: ";

        cin>>c;

        switch (c)
        {
        case 1:
            b.levelorder_newline();
            // to print the tree in level order
            break;
                  
        case 2:
            cout<<"\nEnter no. ";
            cin>>x;
            b.root = b.insert(b.root,x);
            break;
        
        case 3:
            cout<<"\nWhat to delete? ";
            cin>>x;
            b.root = b.deleteNode(b.root,x);
            break;
            
        case 0:
            break;
        }

     } while(c!=0);
  
}

Running example of above code:

1. Copy the code above and paste in "avl.cpp".
2. Compile the code:

g++ avl.cpp -o run

3. Run the code.

./run 

Advantages of AVL Trees

• The height of the AVL tree is always balanced. The height never grows beyond log N, where N is the total number of nodes in the tree.
• It gives better search time complexity when compared to simple Binary Search trees.
• AVL trees have self-balancing capabilities.

Summary:

• AVL trees are self-balancing binary search trees.
• Balance factor is the fundamental attribute of AVL trees
• The balance factor of a node is defined as the difference between the height of the left and right subtree of that node.
• The valid values of the balance factor are -1, 0, and +1.
• The insert and delete operation require rotations to be performed after violating the balance factor.
• The time complexity of insert, delete, and search operation is O(log N).
• AVL trees follow all properties of Binary Search Trees.
• The left subtree has nodes that are lesser than the root node. The right subtree has nodes that are always greater than the root node.
• AVL trees are used where search operation is more frequent compared to insert and delete operations.