Deletion in AVL Tree - Naukri Code 360

Q: What is the balancing condition of an AVL tree?

The balancing condition of an AVL tree is: balance(n) = abs(height(n.left)−height(n.right))

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.

Deleting a node from an AVL tree follows similar principles to a binary search tree. However, it may disrupt the balance factor, requiring the tree to be rebalanced to maintain its AVL property.

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

In this article, we’ll learn about deletion in AVL tree.

Properties of AVL Tree

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 a value of 9 has a balance factor of 2.

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.

Algorithm

AVL Tree is a self-balancing binary search tree. The 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.

Steps to Follow for Deletion in AVL

Here are the steps to follow for deleting a node in an AVL tree:

First, remove the node you want to delete, like when removing a standard item from a list.
After removing the node, go up the tree and update the heights of the nodes. It is like updating the order of the steps when you climb up or down stairs.
Starting from where you deleted the node, go up towards the root. Along the way, check if any node needs to be balanced.
If you find an imbalance, perform rotations (simple or double) to balance the tree.

Example of Deletion in AVL

Consider an AVL tree with nodes 10, 20, 30, 40, 50. Deleting node 30 triggers a left rotation at node 20 to maintain AVL balance.

Implementing deletion in an AVL Tree

C++

#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;
}

You can also try this code with Online C++ Compiler

Run Code

C

#include <stdio.h>
#include <stdlib.h>

typedef struct AVL_Node {
    int key;
    struct AVL_Node *left, *right;
    int height;
} AVL_Node;

int height(AVL_Node *N) {
    return (N == NULL) ? 0 : N->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

AVL_Node* newAVL_Node(int key) {
    AVL_Node* node = (AVL_Node*)malloc(sizeof(AVL_Node));
    node->key = key;
    node->left = node->right = NULL;
    node->height = 1;
    return node;
}

AVL_Node *rightRotate(AVL_Node *y) {
    AVL_Node *x = y->left;
    AVL_Node *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    return x;
}

AVL_Node *leftRotate(AVL_Node *x) {
    AVL_Node *y = x->right;
    AVL_Node *T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    return y;
}

int getBalance(AVL_Node *N) {
    return (N == NULL) ? 0 : height(N->left) - height(N->right);
}

AVL_Node* AVL_insert(AVL_Node* node, int key) {
    if (node == NULL) return newAVL_Node(key);
    if (key < node->key) node->left = AVL_insert(node->left, key);
    else if (key > node->key) node->right = AVL_insert(node->right, key);
    else return node;
    
    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);
    
    if (balance > 1 && key < node->left->key) return rightRotate(node);
    if (balance < -1 && key > node->right->key) return leftRotate(node);
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

AVL_Node* minValueAVL_Node(AVL_Node* node) {
    AVL_Node* current = node;
    while (current && current->left != NULL) current = current->left;
    return current;
}

AVL_Node* AVL_delete(AVL_Node* root, int key) {
    if (root == NULL) return root;
    if (key < root->key) root->left = AVL_delete(root->left, key);
    else if (key > root->key) root->right = AVL_delete(root->right, key);
    else {
        if ((root->left == NULL) || (root->right == NULL)) {
            AVL_Node *temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else *root = *temp;
            free(temp);
        } else {
            AVL_Node* temp = minValueAVL_Node(root->right);
            root->key = temp->key;
            root->right = AVL_delete(root->right, temp->key);
        }
    }
    if (root == NULL) return root;
    root->height = 1 + max(height(root->left), height(root->right));
    int balance = getBalance(root);
    if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root);
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root);
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

void PREORDER(AVL_Node *root) {
    if (root != NULL) {
        printf("%d ", root->key);
        PREORDER(root->left);
        PREORDER(root->right);
    }
}

int main() {
    AVL_Node *root = NULL;
    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);

    printf("Preorder traversal of the above AVL tree is:\n");
    PREORDER(root);
    root = AVL_delete(root, 25);
    printf("\nPreorder traversal after deletion of 25:\n");
    PREORDER(root);
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Java

class AVLNode {
    int key, height;
    AVLNode left, right;

    AVLNode(int d) {
        key = d;
        height = 1;
    }
}

public class AVLTree {
    AVLNode root;

    int height(AVLNode N) {
        return (N == null) ? 0 : N.height;
    }

    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;
        return x;
    }

    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;
        return y;
    }

    int getBalance(AVLNode N) {
        return (N == null) ? 0 : height(N.left) - height(N.right);
    }

    AVLNode insert(AVLNode node, int key) {
        if (node == null) return new AVLNode(key);
        if (key < node.key) node.left = insert(node.left, key);
        else if (key > node.key) node.right = insert(node.right, key);
        else return node;

        node.height = 1 + max(height(node.left), height(node.right));
        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key) return rightRotate(node);
        if (balance < -1 && key > node.right.key) return leftRotate(node);
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    AVLNode minValueNode(AVLNode node) {
        AVLNode current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    AVLNode delete(AVLNode root, int key) {
        if (root == null) return root;
        if (key < root.key) root.left = delete(root.left, key);
        else if (key > root.key) root.right = delete(root.right, key);
        else {
            if ((root.left == null) || (root.right == null)) {
                AVLNode temp = root.left != null ? root.left : root.right;
                if (temp == null) {
                    temp = root;
                    root = null;
                } else root = temp;
            } else {
                AVLNode temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = delete(root.right, temp.key);
            }
        }
        if (root == null) return root;
        root.height = 1 + max(height(root.left), height(root.right));
        int balance = getBalance(root);
        if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root);
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }
        if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root);
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }
        return root;
    }

    void preOrder(AVLNode root) {
        if (root != null) {
            System.out.print(root.key + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 25);
        tree.root = tree.insert(tree.root, 60);
        tree.root = tree.insert(tree.root, 45);
        tree.root = tree.insert(tree.root, 42);
        tree.root = tree.insert(tree.root, 52);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 55);
        tree.root = tree.insert(tree.root, 75);
        tree.root = tree.insert(tree.root, 70);
        tree.root = tree.insert(tree.root, 80);
        tree.root = tree.insert(tree.root, 85);

        System.out.println("Preorder traversal of the above AVL tree is:");
        tree.preOrder(tree.root);
        tree.root = tree.delete(tree.root, 25);
        System.out.println("\nPreorder traversal after deletion of 25:");
        tree.preOrder(tree.root);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def height(self, N):
        return N.height if N else 0

    def max(self, a, b):
        return a if a > b else b

    def rightRotate(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = self.max(self.height(y.left), self.height(y.right)) + 1
        x.height = self.max(self.height(x.left), self.height(x.right)) + 1
        return x

    def leftRotate(self, x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = self.max(self.height(x.left), self.height(x.right)) + 1
        y.height = self.max(self.height(y.left), self.height(y.right)) + 1
        return y

    def getBalance(self, N):
        return self.height(N.left) - self.height(N.right) if N else 0

    def insert(self, node, key):
        if not node:
            return AVLNode(key)
        if key < node.key:
            node.left = self.insert(node.left, key)
        elif key > node.key:
            node.right = self.insert(node.right, key)
        else:
            return node
        
        node.height = 1 + self.max(self.height(node.left), self.height(node.right))
        balance = self.getBalance(node)

        if balance > 1 and key < node.left.key:
            return self.rightRotate(node)
        if balance < -1 and key > node.right.key:
            return self.leftRotate(node)
        if balance > 1 and key > node.left.key:
            node.left = self.leftRotate(node.left)
            return self.rightRotate(node)
        if balance < -1 and key < node.right.key:
            node.right = self.rightRotate(node.right)
            return self.leftRotate(node)

        return node

    def minValueNode(self, node):
        current = node
        while current.left:
            current = current.left
        return current

    def delete(self, root, key):
        if not root:
            return root
        if key < root.key:
            root.left = self.delete(root.left, key)
        elif key > root.key:
            root.right = self.delete(root.right, key)
        else:
            if root.left is None or root.right is None:
                temp = root.left if root.left else root.right
                root = temp if temp else None
            else:
                temp = self.minValueNode(root.right)
                root.key = temp.key
                root.right = self.delete(root.right, temp.key)

        if root is None:
            return root

        root.height = 1 + self.max(self.height(root.left), self.height(root.right))
        balance = self.getBalance(root)

        if balance > 1 and self.getBalance(root.left) >= 0:
            return self.rightRotate(root)
        if balance > 1 and self.getBalance(root.left) < 0:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)
        if balance < -1 and self.getBalance(root.right) <= 0:
            return self.leftRotate(root)
        if balance < -1 and self.getBalance(root.right) > 0:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

    def preOrder(self, root):
        if root:
            print(root.key, end=" ")
            self.preOrder(root.left)
            self.preOrder(root.right)

if __name__ == "__main__":
    tree = AVLTree()
    root = None
    root = tree.insert(root, 40)
    root = tree.insert(root, 20)
    root = tree.insert(root, 10)
    root = tree.insert(root, 30)
    root = tree.insert(root, 25)
    root = tree.insert(root, 60)
    root = tree.insert(root, 45)
    root = tree.insert(root, 42)
    root = tree.insert(root, 52)
    root = tree.insert(root, 50)
    root = tree.insert(root, 55)
    root = tree.insert(root, 75)
    root = tree.insert(root, 70)
    root = tree.insert(root, 80)
    root = tree.insert(root, 85)

    print("Preorder traversal of the above AVL tree is:")
    tree.preOrder(root)
    root = tree.delete(root, 25)
    print("\nPreorder traversal after deletion of 25:")
    tree.preOrder(root)

You can also try this code with Online Python Compiler

Run Code

C#

using System;

class AVLNode {
    public int key, height;
    public AVLNode left, right;

    public AVLNode(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    AVLNode root;

    int height(AVLNode N) {
        return (N == null) ? 0 : N.height;
    }

    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;
        return x;
    }

    AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;
        return y;
    }

    int getBalance(AVLNode N) {
        return (N == null) ? 0 : height(N.left) - height(N.right);
    }

    AVLNode insert(AVLNode node, int key) {
        if (node == null) return new AVLNode(key);
        if (key < node.key) node.left = insert(node.left, key);
        else if (key > node.key) node.right = insert(node.right, key);
        else return node;

        node.height = 1 + max(height(node.left), height(node.right));
        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key) return rightRotate(node);
        if (balance < -1 && key > node.right.key) return leftRotate(node);
        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    AVLNode minValueNode(AVLNode node) {
        AVLNode current = node;
        while (current.left != null) current = current.left;
        return current;
    }

    AVLNode delete(AVLNode root, int key) {
        if (root == null) return root;
        if (key < root.key) root.left = delete(root.left, key);
        else if (key > root.key) root.right = delete(root.right, key);
        else {
            if (root.left == null || root.right == null) {
                AVLNode temp = root.left != null ? root.left : root.right;
                root = temp != null ? temp : null;
            } else {
                AVLNode temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = delete(root.right, temp.key);
            }
        }

        if (root == null) return root;

        root.height = 1 + max(height(root.left), height(root.right));
        int balance = getBalance(root);

        if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root);
        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }
        if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root);
        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }
        return root;
    }

    void preOrder(AVLNode root) {
        if (root != null) {
            Console.Write(root.key + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public static void Main(string[] args) {
        AVLTree tree = new AVLTree();
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 25);
        tree.root = tree.insert(tree.root, 60);
        tree.root = tree.insert(tree.root, 45);
        tree.root = tree.insert(tree.root, 42);
        tree.root = tree.insert(tree.root, 52);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 55);
        tree.root = tree.insert(tree.root, 75);
        tree.root = tree.insert(tree.root, 70);
        tree.root = tree.insert(tree.root, 80);
        tree.root = tree.insert(tree.root, 85);

        Console.WriteLine("Preorder traversal of the above AVL tree is:");
        tree.preOrder(tree.root);
        tree.root = tree.delete(tree.root, 25);
        Console.WriteLine("\nPreorder traversal after deletion of 25:");
        tree.preOrder(tree.root);
    }
}

JavaScript

class AVLNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

class AVLTree {
    height(N) {
        return N ? N.height : 0;
    }

    max(a, b) {
        return (a > b) ? a : b;
    }

    rightRotate(y) {
        const x = y.left;
        const T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = this.max(this.height(y.left), this.height(y.right)) + 1;
        x.height = this.max(this.height(x.left), this.height(x.right)) + 1;
        return x;
    }

    leftRotate(x) {
        const y = x.right;
        const T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = this.max(this.height(x.left), this.height(x.right)) + 1;
        y.height = this.max(this.height(y.left), this.height(y.right)) + 1;
        return y;
    }

    getBalance(N) {
        return N ? this.height(N.left) - this.height(N.right) : 0;
    }

    insert(node, key) {
        if (!node) return new AVLNode(key);
        if (key < node.key) node.left = this.insert(node.left, key);
        else if (key > node.key) node.right = this.insert(node.right, key);
        else return node;

        node.height = 1 + this.max(this.height(node.left), this.height(node.right));
        const balance = this.getBalance(node);

        if (balance > 1 && key < node.left.key) return this.rightRotate(node);
        if (balance < -1 && key > node.right.key) return this.leftRotate(node);
        if (balance > 1 && key > node.left.key) {
            node.left = this.leftRotate(node.left);
            return this.rightRotate(node);
        }
        if (balance < -1 && key < node.right.key) {
            node.right = this.rightRotate(node.right);
            return this.leftRotate(node);
        }
        return node;
    }

    minValueNode(node) {
        let current = node;
        while (current.left) current = current.left;
        return current;
    }

    delete(root, key) {
        if (!root) return root;
        if (key < root.key) root.left = this.delete(root.left, key);
        else if (key > root.key) root.right = this.delete(root.right, key);
        else {
            if (!root.left || !root.right) {
                const temp = root.left ? root.left : root.right;
                root = temp ? temp : null;
            } else {
                const temp = this.minValueNode(root.right);
                root.key = temp.key;
                root.right = this.delete(root.right, temp.key);
            }
        }

        if (!root) return root;

        root.height = 1 + this.max(this.height(root.left), this.height(root.right));
        const balance = this.getBalance(root);

        if (balance > 1 && this.getBalance(root.left) >= 0) return this.rightRotate(root);
        if (balance > 1 && this.getBalance(root.left) < 0) {
            root.left = this.leftRotate(root.left);
            return this.rightRotate(root);
        }
        if (balance < -1 && this.getBalance(root.right) <= 0) return this.leftRotate(root);
        if (balance < -1 && this.getBalance(root.right) > 0) {
            root.right = this.rightRotate(root.right);
            return this.leftRotate(root);
        }
        return root;
    }

    preOrder(root) {
        if (root) {
            process.stdout.write(root.key + " ");
            this.preOrder(root.left);
            this.preOrder(root.right);
        }
    }
}

const tree = new AVLTree();
let root = null;
root = tree.insert(root, 40);
root = tree.insert(root, 20);
root = tree.insert(root, 10);
root = tree.insert(root, 30);
root = tree.insert(root, 25);
root = tree.insert(root, 60);
root = tree.insert(root, 45);
root = tree.insert(root, 42);
root = tree.insert(root, 52);
root = tree.insert(root, 50);
root = tree.insert(root, 55);
root = tree.insert(root, 75);
root = tree.insert(root, 70);
root = tree.insert(root, 80);
root = tree.insert(root, 85);

console.log("Preorder traversal of the above AVL tree is:");
tree.preOrder(root);
root = tree.delete(root, 25);
console.log("\nPreorder traversal after deletion of 25:");
tree.preOrder(root);

You can also try this code with Online Javascript Compiler

Run Code

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.

Advantages of AVL Trees

AVL trees are more likely to be balanced than other types of trees. It is also referred to as a "self-balancing binary search tree."
The primary advantage of AVL trees is that they perform better than BSTs, red-black trees, etc., in terms of search operations.
Better than other trees, such as the binary tree, in terms of searching time complexity.
Low-time complexity is required to add or delete nodes.

Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

How do you balance an AVL tree after deletion?

After deleting a node in an AVL tree, ensure the remaining nodes are evenly spaced. To do this, adjust the heights of the nearby nodes and do rotations if needed. Start from the deleted node's parent and work upwards. Rotate as necessary to balance the tree.

What is the balancing condition of an AVL tree?

The balancing condition of an AVL tree is:
balance(n) = abs(height(n.left)−height(n.right))

What is deletion in AVL tree?

The deletion process is the same in both the AVL tree and the BST. An AVL tree needs to be rebalanced because deletion may affect its balance factor. Each node's balance factor is updated through rotation operations.

Can we delete the root node in the AVL tree?

Yes, you can delete the root node in the AVL Tree. First, find the node's in-order successor and copy the contents of the in-order successor to the root node. Then delete the in-order successor. After deleting rebalance the AVL tree.

How do I delete an AVL tree?

To delete an AVL tree, recursively delete all nodes starting from the leaves to the root, ensuring proper adjustment of tree balances during deletion.

What function is first called for removing a node from an AVL tree?

The function first called for removing a node from an AVL tree is the deletion function, which handles node removal and tree rebalancing.

Conclusion

In this blog, we have discussed Deletion in AVL Tree. This ensures the tree remains balanced for efficient operations. Through rotations and adjustments, AVL tree deletion maintains stability, making it a fundamental tool for managing data effectively. Embracing these principles empowers developers to handle dynamic datasets with ease and confidence.

Suggested Readings: