Deletion in AVL Tree
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.
- Introduction to AVL Trees
- Insertion in AVL Tree
- 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:
- It is a binary search tree, and
- 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:
- After the node is deleted, start from its parent, move up to the tree's root, and check for the first unbalanced node.
- 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
- 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).
- 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.
- 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))
- 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!
Previous Article 
Comments
No comments yet
Be the first to share what you think