Deletion in AVL Tree

vaishnavi pandey
Last Updated: May 13, 2022

Introduction

Adelson-Velskii and Landis (AVL) is a type of Binary Search Tree. In the AVL tree, the difference between the height of the left and right subtree is at most 1. This difference is known as the balance factor.

 

This article is a part of three blog series on AVL trees. The contents of the three blogs are divided as follows.

  1. Introduction to AVL Trees
  2. Insertion in AVL Tree
  3. Deletion in AVL Tree

 

In this article, we’ll learn about deleting a node from the AVL tree. 

AVL Tree Properties 

A binary tree is an AVL tree, if:

  1. It is a binary search tree, and
  2. For any node A, the height of the left subtree of A and the height of the right subtree of A differ by at most 1.






Figure 1 Figure 2

 

For example, among the above binary search trees, Figure 1 is an AVL tree, whereas Figure 2 is not. The reason is, in figure 2, the node having value 9 has a balance factor of 2.

Modification/ Deletion in an AVL Tree

When we insert or delete an element in a tree, its structure changes. To restore the AVL tree property, we need to modify the tree. This can be done using rotations. 

 

An insertion or deletion involves adding or deleting a single node. This can only increase or decrease the height of a subtree by 1. After every operation, the AVL tree can be restored by using single or double rotation. To revise the concept of rotation in AVL trees do visit here.

Algorithm 

AVL Tree is a self-balancing binary search tree. Deletion of a node will be the same as in BST. After a node has been deleted according to BST, we’ll check for the unbalanced nodes(Nodes having a balance factor of more than 1).
 

The remaining steps are as follows:

  1. After the node is deleted, start from its parent, move up to the tree's root, and check for the first unbalanced node. 
  2. Restore the AVL tree property by performing one of the following rotations.


To know more about rotations and how they are performed, you can visit this amazing article on Introduction to AVL Trees.

 

Let’s understand what is the basic difference between the two main operations i.e. Insertion and Deletion.

Difference between Insertion and Deletion in AVL Tree

Insertion: After an insertion, subtrees of the node are changed, resulting in the change of balance factor in the path from the point of insertion to the root. We need to restore the AVL tree property.


We need to consider the first node with a balance factor greater than one while moving to the root. Starting from this node, every node till the root will have the issue.

If we fix the issue here, then all other nodes will automatically satisfy the AVL tree property. 


For learning more about insertion in AVL trees and their Implementation, refer to Part-2 of the series.


Deletion: 

In contrast to insertion, after performing a rotation at a node to restore the AVL property, we may need to perform a rotation at that node's ancestors. As a result, we must follow the path until we reach the root.

 

Let’s understand this with the help of an example.

Understand deleting a node from the AVL tree with the help of an example

 

Given an AVL Tree:

Step 1: Deleting node 0025.

The tree will become this: 

This is not balanced(the node 0040 has a balanced factor of 2), Hence, Not an AVL tree. 

 

Step 2: Start from 0030, move till the root, i.e. 0040. Find the first unbalanced node. 

The first unbalanced node is 0040(Having a balance factor of 2).

 

Step 3: Perform rotation to make it balanced.

This is a balanced AVL Tree.

Implementing Deletion in an AVL Tree

#include<bits/stdc++.h>

using namespace std;

 

class AVL_Node

{

public:

int key;

AVL_Node *left;

AVL_Node *right;

int height;

};

 

// Function to get the height of the tree

int height(AVL_Node *N)

{

if (N == NULL)

return 0;

return N->height;

}

 

// Function to get a maximum of two integers

int max(int a, int b)

{

return (a > b)? a : b;

}

 

//Function to create a new AVL_Node 

//Adding the newly created node as leaf node

AVL_Node* newAVL_Node(int key)

{

AVL_Node* node = new AVL_Node();

node->key = key;

node->left = NULL;

node->right = NULL;

node->height = 1;

return(node);

}

 

// Function for right rotation

AVL_Node *rightRotate(AVL_Node *y)

{

AVL_Node *x = y->left;

AVL_Node *T2 = x->right;

 

// Perform rotation

x->right = y;

y->left = T2;

 

// Update heights

y->height = max(height(y->left),height(y->right)) + 1;

x->height = max(height(x->left),height(x->right)) + 1;

 

// Return new root

return x;

}

 

// Function for left rotation

AVL_Node *leftRotate(AVL_Node *x)

{

AVL_Node *y = x->right;

AVL_Node *T2 = y->left;

 

// Perform rotation

y->left = x;

x->right = T2;

 

// Update heights

x->height = max(height(x->left),height(x->right)) + 1;

y->height = max(height(y->left),height(y->right)) + 1;

 

// Return new root

return y;

}

 

// Function to find the Balance factor of Nodes

int getBalance(AVL_Node *N)

{

if (N == NULL)

return 0;

return height(N->left) - height(N->right);

}

 

//Function to construct a tree.

AVL_Node* AVL_insert(AVL_Node* AVL_Node, int key)

{

//Perform the normal BST insertion

if (AVL_Node == NULL)

return(newAVL_Node(key));

 

if (key < AVL_Node->key)

AVL_Node->left = AVL_insert(AVL_Node->left, key);

else if (key > AVL_Node->key)

AVL_Node->right = AVL_insert(AVL_Node->right, key);

else 

return AVL_Node;

 

//Update height of ancestor Node

AVL_Node->height = 1 + max(height(AVL_Node->left),height(AVL_Node->right));

 

//Step 1: Find the balance factor of parent

int balance = getBalance(AVL_Node);

 

// If this Node becomes unbalanced, all four cases are:

 

// 1. Left Left Case

if (balance > 1 && key < AVL_Node->left->key)

return rightRotate(AVL_Node);

 

// 2. Right Right Case

if (balance < -1 && key > AVL_Node->right->key)

return leftRotate(AVL_Node);

 

// 3. Left Right Case

if (balance > 1 && key > AVL_Node->left->key)

{

AVL_Node->left = leftRotate(AVL_Node->left);

return rightRotate(AVL_Node);

}

 

// 4. Right Left Case

if (balance < -1 && key < AVL_Node->right->key)

{

AVL_Node->right = rightRotate(AVL_Node->right);

return leftRotate(AVL_Node);

}

 

//Return the (unchanged) Node pointer

return AVL_Node;

}

 

//Function to find the AVL_Node with minimum key value

AVL_Node * minValueAVL_Node(AVL_Node* node)

{

AVL_Node* current = node;

 

//Going to the left most side

while (current->left != NULL)

current = current->left;

 

return current;

}

 

//Function to delete an AVL_Node with the given key from the subtree 

AVL_Node* AVL_delete(AVL_Node* root, int key)

{

 

//Perform normal BST deletion

if (root == NULL)

return root;

 

//Find the node to be deleted

//Left Side

if ( key < root->key )

root->left = AVL_delete(root->left, key);

 

//Right Side

else if( key > root->key )

root->right = AVL_delete(root->right, key);

    //Root Node

else

{

// AVL_Node with only one child or no child

if( (root->left == NULL) || (root->right == NULL) )

{

AVL_Node *temp = root->left ? root->left : root->right;

 

// No child case

if (temp == NULL)

{

temp = root;

root = NULL;

}

else // One child case

*root = *temp; // Copy the contents of the non-empty child

free(temp);

}

else

{

// AVL_Node with two children: Get the inorder

// successor (smallest in the right subtree)

AVL_Node* temp = minValueAVL_Node(root->right);

 

// Copy the inorder successor's

// data to this AVL_Node

root->key = temp->key;

 

// Delete the inorder successor

root->right = AVL_delete(root->right,temp->key);

}

}

 

// If the tree had only one AVL_Node then return

if (root == NULL)

return root;

 

//UPDATE HEIGHT OF THE CURRENT AVL_Node

root->height = 1 + max(height(root->left),height(root->right));

 

//GET THE BALANCE FACTOR OF THIS AVL_Node (to check whether this AVL_Node became unbalanced)

int balance = getBalance(root);

 

// If this AVL_Node becomes unbalanced, then there are 4 cases

 

// Left Left Case

if (balance > 1 &&

getBalance(root->left) >= 0)

return rightRotate(root);

 

// Left Right Case

if (balance > 1 &&

getBalance(root->left) < 0)

{

root->left = leftRotate(root->left);

return rightRotate(root);

}

 

// Right Right Case

if (balance < -1 &&

getBalance(root->right) <= 0)

return leftRotate(root);

 

// Right Left Case

if (balance < -1 &&

getBalance(root->right) > 0)

{

root->right = rightRotate(root->right);

return leftRotate(root);

}

 

return root;

}

 

//  AVL Tree Traversal 

 

void PREORDER(AVL_Node *root)

{

if(root != NULL)

{

cout << root->key << " ";

PREORDER(root->left);

PREORDER(root->right);

}

}

 

int main()

{

AVL_Node *root = NULL;

 

//Constructing tree 

root = AVL_insert(root, 40);

root = AVL_insert(root, 20);

root = AVL_insert(root, 10);

root = AVL_insert(root, 30);

root = AVL_insert(root, 25);

root = AVL_insert(root, 60);

root = AVL_insert(root, 45);

root = AVL_insert(root, 42);

root = AVL_insert(root, 52);

root = AVL_insert(root, 50);

root = AVL_insert(root, 55);

root = AVL_insert(root, 75);

root = AVL_insert(root, 70);

root = AVL_insert(root, 80);

root = AVL_insert(root, 85);

 

cout << "Preorder traversal of the above AVL tree is:\n"<<endl;

PREORDER(root);

//Deleting the node 25

    root = AVL_delete(root, 25);

 

cout <<endl<<"Preorder traversal after"<< " deletion of 25:\n"<<endl;

PREORDER(root);

 

return 0;

}

 

Output:

Preorder traversal of the above AVL tree is:

 

45 30 20 10 25 40 42 60 52 50 55 75 70 80 85

Preorder traversal after deletion of 25:

 

45 30 20 10 40 42 60 52 50 55 75 70 80 85



 

 

 

Complexity Analysis

 

Time Complexity:

The time complexity of an AVL delete is the same as that of a BST delete, which is O(h), where h is the height of the tree. Rotation, updating the height and getting the balance factor takes constant time.  

The height of the AVL tree is O(logn) since it is balanced. As a result, the AVL delete has an O(log n) time complexity.

 

Space Complexity:

For deleting an element, we have to traverse the tree to find it. Space complexity depends on the number of stack frames required in the recursive traversal. 

The space complexity of a recursive in-order traversal is O(h), where h is the height of the tree. The height of the AVL tree is O(logn) since it is balanced. As a result, the AVL delete has an O(log n) space complexity.

Frequently asked questions

  1. What is the maximum height of an AVL tree having n nodes?
    Answer: The maximum height of an AVL tree having n nodes is log(n).
     
  2. State two properties of AVL trees.Answer: 
    Answer: The important properties of an AVL tree are:
    → It is a binary search tree,
    → andFor any node A, the height of the left subtree of A and the height of the right subtree of A differ by at most 1.
     
  3. What is the balancing condition of an AVL tree?
    Answer: The balancing condition of an AVL tree is: 
    balance(n) = abs(height(n.left)−height(n.right))
     
  4. What is the time complexity of deleting a node from the AVL tree?
    Answer: Due to the balancing property, the deletion operations take O ( l o g n ) time in both the average and the worst cases.

 

Key Takeaways

Here's a treat for you, you can create your AVL tree by inserting and deleting nodes virtually. You can also see how these rotations work on this fantastic AVL Tree Virtualization webpage.

In this article, we learned about deleting a node from the AVL tree along with its proper implementation in C++.

To get a complete insight into AVL trees, we recommend reading this series on AVL trees. 

Happy Learning!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think