Deletion In AVL Tree In C++

March 4, 2023

C++ Program For Deletion 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.

Deletion in an AVL Tree

Deletion in an AVL tree is similar to that in a BST.
Deletion of a node tends to disturb the balance factor. Thus to balance the tree, we again use the Rotation mechanism.
Deletion in AVL tree consists of two steps:
- Removal of the node: The given node is removed from the tree structure. The node to be removed can either be a leaf or an internal node.
- Re-balancing of the tree: The elimination of a node from the tree can cause disturbance to the balance factor of certain nodes. Thus it is important to re- balance theb_fact of the nodes; since the balance factor is the primary aspect that ensures the tree is an AVL Tree.

Note: There are certain points that must be kept in mind during a deletion process.

If the node to be deleted is a leaf node, it is simply removed from the tree.
If the node to be deleted has one child node, the child node is replaced with the node to be deleted simply.
If the node to be deleted has two child nodes then,
- Either replace the node with it’s inorder predecessor , i.e, the largest element of the left sub tree.
- Or replace the node with it’s inorder successor , i.e, the smallest element of the right sub tree.

Let us consider the same example as above with some additional elements as shown.

We can see in the image the balance factor of each node in the tree.

AVL Trees

AVL Tree Deletion

Insertion in a Binary Tree (Level Order)

Searching in Binary Tree

Searching in a Binary Search Tree

Step 1:

The node to be deleted from the tree is 8.
If we observe it is the parent node of the node 5 and 9.
Since the node 8 has two children it can be replaced by either of it’s child nodes.

Step 2:

The node 8 is deleted from the tree.
As the node is deleted we replace it with either of it’s children nodes.
Here we replaced the node with the inorder successor , i.e, 9.
Again we check the balance factor for each node.

Step 3:

Now The next element to be deleted is 12.
If we observe, we can see that the node 12 has a left subtree and a right subtree.
We again can replace the node by either it’s inorder successor or inorder predecessor.
In this case we have replaced it by the inorder successor.

Step 4:

The node 12 is deleted from the tree.
Since we have replaced the node with the inorder successor, the tree structure looks like shown in the image.
After removal and replacing check for the balance factor of each node of the tree.

Step 5:

The next node to be eliminated is 14.
It can be seen clearly in the image that 14 is a leaf node.
Thus it can be eliminated easily from the tree.

Step 6:

As the node 14 is deleted, we check the balance factor of all the nodes.
We can see the balance factor of the node 13 is 2.
This violates the terms of the AVL tree thus we need to balance it using the rotation mechanism.

Prime Course Trailer

Alert In step 6 you can see the violation of AVL tree

Related Banners

Step 7:

In order to balance the tree, we identify the rotation mechanism to be applied.
Here we need to use LL Rotation.
The nodes involved in the rotation is shown as follows.

Step 8:

The nodes are rotated and the tree satisfies the conditions of an AVL tree.
The final structure of the tree is shown as follows.
We can see all the nodes have their balance factor as ‘0’ , ‘1’ and ‘-1’.

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

C++ Code For Deletion In AVL Tree

Run

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

};

node *insert(node *,int);
node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
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. Delete Element\n“;
        cout << “3. 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;
             
            case 2: cout << “Enter a element to be deleted : “;
                    cin >> x;
                    root = Delete(root,x);
                    cout << “Preorder sequence:\n“;
                    preorder(root);
                    cout << “\nInorder sequence:\n“;
                    inorder(root);
                    break;
        }
    }while(option!=3);

    return 0;

}

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

    if(T == NULL){

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

        if(x > T->element)        
        {

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

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

            }

        T -> ht = height(T);

        return(T);
}
node * Delete(node *T,int x)
{
    node *p;

    if(T == NULL)
    {
        return NULL;
    }
    else
        if(x > T->element)    
        {
            T -> right = Delete(T -> right,x);
            if(balanceFactor(T) == 2)
                if(balanceFactor(T -> left) >= 0)
                    T = LL(T);
                else
                    T = LR(T);
        }
        else
            if(x < T -> element)
            {
                T -> left = Delete(T->left,x);
                if(balanceFactor(T)==-2)    
                    if(balanceFactor(T->right)<=0)
                        T=RR(T);
                    else
                        T=RL(T);
            }
            else
            {
                if(T -> right != NULL)
                {
                    p = T -> right;

                    while(p -> left != NULL)
                        p = p -> left;

                    T -> element = p -> element;
                    T -> right = Delete(T -> right,p->element);

                    if(balanceFactor(T) == 2)
                        if(balanceFactor (T -> left) >= 0)
                            T=LL(T);
                        else
                            T=LR(T);\
                }
                else
                    return(T->left);
            }
    T ->ht = height(T);
    return(T);
}
int height(node *T)
{

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

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

    if(lh > rh)
        return(lh);

    return(rh);
}

node * rotateright(node *x)
{

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

node * rotateleft(node *x)
{
    node *y;
    y = x -> right;
    x -> right = y -> left;
    y -> left = x;
    x -> ht = height(x);
    y -> 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)
{

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

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

void preorder(node *T)
{
    if( T != NULL)
    {
        cout << “Balance factor “ << T -> 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. Delete Element
3. End Program
Enter your choice 1

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

Preorder sequence:
Balance factor 15 0
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 1
Balance factor 16 0
Balance factor 60 0
Balance factor 56 0
Balance factor 70 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 0
Balance Factor 16 0
Balance Factor 18 1
Balance Factor 54 0
Balance Factor 56 0
Balance Factor 60 0
Balance Factor 70 0
1. Create AVL Tree
2. Delete Element
3. End Program
Enter your choice 2
Enter a element to be deleted : 8
Preorder sequence:
Balance factor 15 0
Balance factor 12 0
Balance factor 9 1
Balance factor 5 0
Balance factor 13 -1
Balance factor 14 0
Balance factor 54 0
Balance factor 18 1
Balance factor 16 0
Balance factor 60 0
Balance factor 56 0
Balance factor 70 0

Inorder sequence:
Balance Factor 5 0
Balance Factor 9 1
Balance Factor 12 0
Balance Factor 13 -1
Balance Factor 14 0
Balance Factor 15 0
Balance Factor 16 0
Balance Factor 18 1
Balance Factor 54 0
Balance Factor 56 0
Balance Factor 60 0
Balance Factor 70 0
1. Create AVL Tree
2. Delete Element
3. End Program
Enter your choice 1 2
Enter a element to be deleted : 12
Preorder sequence:
Balance factor 15 0
Balance factor 13 1
Balance factor 9 1
Balance factor 5 0
Balance factor 14 0
Balance factor 54 0
Balance factor 18 1
Balance factor 16 0
Balance factor 60 0
Balance factor 56 0
Balance factor 70 0

Inorder sequence:
Balance Factor 5 0
Balance Factor 9 1
Balance Factor 13 1
Balance Factor 14 0
Balance Factor 15 0
Balance Factor 16 0
Balance Factor 18 1
Balance Factor 54 0
Balance Factor 56 0
Balance Factor 60 0
Balance Factor 70 0
1. Create AVL Tree
2. Delete Element
3. End Program
Enter your choice 2
Enter a element to be deleted : 14
Preorder sequence:
Balance factor 15 -1
Balance factor 9 0
Balance factor 5 0
Balance factor 13 0
Balance factor 54 0
Balance factor 18 1
Balance factor 16 0
Balance factor 60 0
Balance factor 56 0
Balance factor 70 0

Inorder sequence:
Balance Factor 5 0
Balance Factor 9 0
Balance Factor 13 0
Balance Factor 15 -1
Balance Factor 16 0
Balance Factor 18 1
Balance Factor 54 0
Balance Factor 56 0
Balance Factor 60 0
Balance Factor 70 0
1. Create AVL Tree
2. Delete Element
3. End Program
Enter your choice 3

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal Line by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric – C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree- C | C++ | Java

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal LIne by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree. C | C++ | Java

Unlock this article for Free,
by logging in

Deletion In AVL Tree In C++

C++ Program For Deletion In AVL Tree: