Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Insertion in AVL Tree In C++

Insertion In AVL Tree

AVL tree is self balancing tree in which for all nodes, the difference of height between the left subtree and the right subtree is less than or equal to 1. In this article, an avl tree is created and the difference of height is printed for each node.

 

C++ Program To Delete Value in AVL Tree

Insertion and Creation of an AVL Tree

  • A new node can be inserted in an AVL tree by determining the correct position of the node. But insertion of a new node into the tree may affect the height of the tree and the tree might become unbalanced.
  • If the new nodes are inserted as child nodes on a non- leaf node there will be no alteration since there will be no effect on the balancing as there is no increase in the height of the tree.
  • If the new nodes are inserted as child nodes on a leaf node, the balancing of the tree might get distorted. This depends on whether the node is added to the left subtree or the right subtree.
  • Thus to re-balance the tree in order to conserve it’s characteristics we use Rotation Mechanism. There are four types of rotations which help maintain the balancing of the tree as specified above.
  • If, due to insertion,the b_fact of multiple nodes is disturbed, balancing occurs on the first ancestor of the node that has been inserted.

Note: During the process of insertion it is important to check the balancing factor of each node at each step, until the process end.

Let us understand with the help of an example. Consider we have following elements given to us: [ 15 , 18 , 12 , 8 , 54 , 5 , 14 , 13 , 9 , 60].

Step 1:

  • Insert the first element 15.
  • Check for the b_fact of the node.
  • b_fact= 0

Step 2:

  • Insert the next element 18.
  • Check the b_fact each node.

Step 3:

  • Insert the next element .
  • Check for the b_fact each node.
  • The b_fact of each node in this case is 0.

Step 4:

  • Insert the next element 8.
  • Check for the b_fact of each node.
Working - Steps 1-4 - C++ Program to insert value in AVL

Step 5:

  • Insert the next element 54.
  • Check if the b_fact is anything other than -1 , 0 , 1.

Step 6:

  • Insert the next element 5.
  • Check the b_fact of each node.
  • We can see the b_fact of the node 12 is 2. The tree becomes unbalanced.
  • We have to balance the tree by identifying the rotation mechanism to be applied. 

Step 7:

  • We observe the element is inserted to the ,left of the left subtree.
  • Thus we have to apply LL Rotation.
  • The nodes involved in the rotation are shown in red.
Working Steps 5-7 C++ Program to insert value in AVL

Step 8:

  • In order to balance the tree, the tree is rotated towards the right.
  • In this case the new parent is 8 and the nodes and 12 becomes the child nodes.

Step 9:

  • The next element inserted in the tree is 14.
  • Again check the b_fact of each node of the tree.

Step 10:

  • The next element to be inserted in the tree is 13.
  • After the insertion of the new node, we check for the  b_fact of each node.
  • Now due to the latest insertion to the tree we can see that the balancing factor of multiple nodes is distorted
  • We look for the first ancestor on which the balance factor is disturbed.
  • We identify the rotation mechanism to be used.

Step 11:

  • To balance the tree we use the RL Rotation Mechanism
  • We identify the nodes that are involved in thre rotation mechanism which are shown in red.

Step 12:

  • In this scenario, first a right rotation is applied.
  • The tree after right rotation is shown as follows.
 

Step 13:

  • Now to balance the tree, we apply a left rotation. 
  • After the rotation, the node 13 becomes the new parent node and the nodes 12 and 14 become the new child nodes.
  • If we check the balance factor for each node, the balance factor is eithe 0 , 1 or -1.
Working steps 11-13 C++ Program to insert value in AVl tree

Step 14:

  • The next element to be inserted is 9.
  • As the new element is inserted, we observe that the balance factor of the node 8 becomes (-2).

Step 15:

  • We can see from the image that for balancing the tree we need to apply RL Rotation. 
  • Again, first a right rotation is applied and then a left rotation is applied to the tree structure.

Step 16:

  • After applying the RL Rotation, the tree structure with the optimal b_fact is shown as follows.
  • We can see that the b_fact ranges between 0 , 1 and -1.
  • Thus it is an AVL tree.

Step 17:

  • The next element to be inserted is 60.
  • As 60 is inserted the b_fact of the nodes of right subtree is disturbed.

Step 18:

  • Since the disturbance in the balance factor is due to the insertion of an element to the right of the right subtree, we use RR Rotation.

Step 19:

  • After applying the RR Rotation the tree so obtained is shown below.
  • All the nodes satisfy the condition of an AVL tree.
  • The final tree at the end of insertion process with balanced nodes is shown below.
Working Step 19 - C++ Program to insert value in tree

Code:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int element;
    struct node *left,*right;
    int ht;

};

node *insert(node *,int);
void preorder(node *);
void inorder(node *);
int heightnode *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int balanceFactor(node *);
int main()
{
    node *root=NULL;
    int x,n,i,option;
    do {
        cout << “1. Create AVL Tree\n;
        cout << “2. End Program\n;
        cout << “Enter your choice “;
        cin >> option;
        switch(option)
        {
            case 1: cout << \nEnter no. of elements : “;
                    cin >> n;
                    root = NULL;
                    for( i = 0; i < n;i++) {

                        cout << “Enter element of tree “;
                        cin >> x;
                        root = insert(root,x);
                    }
                    cout << \nPreorder sequence:\n;
                    preorder(root);
                    cout << \n\nInorder sequence:\n;
                    inorder(root);
                    break;
        }
    }while(option!=2);

    return 0;

}

node * insert(node *T,int x)
{

    if(T == NULL){

        T = (node*)malloc(sizeof(node));
        -> element = x;
        -> left = NULL;
        -> right = NULL;
    }
    else

        if(x > T->element)        
        {

            -> right = insert(-> right,x);
            if(balanceFactor(T) == –2)
                if( x > -> right -> element)
                    T = RR(T);
                else
                    T = RL(T);

        }
        else
            if(x<T->element)
            {
                -> left = insert(-> left,x);
                if(balanceFactor(T)==2)
                    if(x < T-> left -> element)
                        T=LL(T);
                    else
                        T=LR(T);

            }

        -> ht = height(T);

        return(T);
}
int height(node *T)
{

    int lh,rh;
    if(T == NULL)
        return(0);
    if-> left == NULL)
        lh = 0;
    else
        lh = 1 + -> left -> ht;

    if(-> right == NULL)
        rh = 0;
    else
        rh=1+T->right->ht;

    if(lh > rh)
        return(lh);

    return(rh);
}

node * rotateright(node *x)
{

    node *y;
    y = -> left;
    -> left = -> right;
    -> right = x;
    -> ht = height(x);
    -> ht = height(y);
    return(y);
}

node * rotateleft(node *x)
{
    node *y;
    y = -> right;
    -> right = -> left;
    -> left = x;
    -> ht = height(x);
    -> ht = height(y);
    return(y);
}

node * RR(node *T)
{

    T = rotateleft(T);
    return(T);
}

node * LL(node *T)
{
    T = rotateright(T);
    return(T);
}

node * LR(node *T)
{

    -> left = rotateleft(T->left);
    T = rotateright(T);
    return(T);
}

node * RL(node *T)
{
    -> right = rotateright(T->right);
    T = rotateleft(T);
    return(T);
}
int balanceFactor(node *T)
{
    int lh,rh;
    if( T == NULL)
        return(0);
    if(-> left == NULL)
        lh = 0;
    else
        lh = 1 + T->left->ht;
    if(-> right == NULL)
        rh = 0;
    else
        rh = 1 + -> right -> ht;
    return(lh-rh);
}

void preorder(node *T)
{
    if( T != NULL)
    {
        cout << “Balance factor “ << -> element << ” “ << balanceFactor(T) << endl;
        preorder(T->left);
        preorder(T->right);
    }
}
void inorder(node *T)
{

    if( T != NULL)
    {
        inorder(T->left);
        cout << “Balance Factor “<<-> element<<” “ << balanceFactor(T) << endl;
        inorder(T->right);
    }
}

 

Output:

1. Create AVL Tree
2. End Program
Enter your choice 1

Enter no. of elements : 10
Enter element of tree 15
Enter element of tree 18
Enter element of tree 12
Enter element of tree 8
Enter element of tree 54
Enter element of tree 5
Enter element of tree 14
Enter element of tree 13
Enter element of tree 9
Enter element of tree 60

Preorder sequence:
Balance factor 15 1
Balance factor 12 0
Balance factor 8 0
Balance factor 5 0
Balance factor 9 0
Balance factor 13 -1
Balance factor 14 0
Balance factor 54 0
Balance factor 18 0
Balance factor 60 0


Inorder sequence:
Balance Factor 5 0
Balance Factor 8 0
Balance Factor 9 0
Balance Factor 12 0
Balance Factor 13 -1
Balance Factor 14 0
Balance Factor 15 1
Balance Factor 18 0
Balance Factor 54 0
Balance Factor 60 0
1. Create AVL Tree
2. End Program
Enter your choice 2

Time Complexity For Insertion In AVL Tree

Time Complexity

O(n)

Space Complexity

O(n)