AVL tree deletion
AVL trees are a type of selfbalancing binary search tree that maintains their height difference (balance factor) between left and right subtrees within a certain range. This selfbalancing property ensures that the tree remains efficient for insertion, deletion, and search operations. In this article, we'll delve into the process of deleting nodes from an AVL tree while maintaining its balance, accompanied by illustrative examples.
First important thing, When we are remove a node from AVL tree. Then tree should be a balanced BST. This is important properties. We can do this using of AVL tree rotation. You can see those rotations by this animation. See AVL Tree Animation.
Problem Statement and Description
The problem at hand is to implement the deletion operation for AVL trees while ensuring that the tree remains balanced. When a node is deleted from an AVL tree, the balance factor of each node along the path from the deleted node to the root needs to be checked and adjusted if necessary to maintain the AVL property.
Example
Consider the following AVL tree:
12
/ \
7 17
/ \ \
3 11 19
/ \
2 5
Let's go through the deletion process of node 12:
 Find the inorder successor (the smallest node in the right subtree, which is 13).
 Replace the value of node 12 with the value of its inorder successor (13).
 Delete the inorder successor (13).
After deletion, the tree will become:
13
/ \
7 17
/ \ \
3 11 19
/ \
2 5
Idea to Solve
The deletion operation in AVL trees can be broken down into several steps:
 Perform a regular binary search tree delete operation.
 Update the height of the current node.
 Check the balance factor to determine if the tree has become unbalanced.
 Apply rotation operations (single or double rotations) to restore balance.
Pseudocode
function deleteNode(root, key):
if root is NULL:
return root
if key < root.data:
root.left = deleteNode(root.left, key)
else if key > root.data:
root.right = deleteNode(root.right, key)
else:
if root.left is NULL or root.right is NULL:
temp = root.left if root.left is not NULL else root.right
if temp is NULL:
temp = root
root = NULL
else:
root = temp
free(temp)
else:
temp = findMinKeyNode(root.right)
root.data = temp.data
root.right = deleteNode(root.right, temp.data)
if root is NULL:
return root
root.height = 1 + max(height(root.left), height(root.right))
balance = getBalanceFactor(root)
if balance > 1 and getBalanceFactor(root.left) >= 0:
return rightRotate(root)
if balance > 1 and getBalanceFactor(root.left) < 0:
root.left = leftRotate(root.left)
return rightRotate(root)
if balance < 1 and getBalanceFactor(root.right) <= 0:
return leftRotate(root)
if balance < 1 and getBalanceFactor(root.right) > 0:
root.right = rightRotate(root.right)
return leftRotate(root)
return root
Algorithm Explanation
 The pseudocode outlines the process of deleting a node from an AVL tree while ensuring that the tree remains balanced.
 The
deleteNode
function is recursive and follows the steps described earlier.  It first performs a standard BST delete operation.
 Then it updates the height of the current node and checks the balance factor.
 Depending on the balance factor and subtree configurations, rotation operations are applied to restore balance.
Code Solution

1) AVL tree deletion in c
2) AVL tree deletion in java
3) AVL tree deletion in c++
4) AVL tree deletion in golang
5) AVL tree deletion in c#
6) AVL tree deletion in vb.net
7) AVL tree deletion in php
8) AVL tree deletion in node js
9) AVL tree deletion in typescript
10) AVL tree deletion in python
11) AVL tree deletion in ruby
12) AVL tree deletion in scala
13) AVL tree deletion in swift
14) AVL tree deletion in kotlin
Time Complexity
The time complexity of deletion in an AVL tree is O(log n), where n is the number of nodes in the tree. The reason is that deletion involves traversing from the root to the node to be deleted, and then balancing the tree using rotations, which takes logarithmic time due to the balanced nature of the AVL tree.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment