AVL tree deletion

AVL trees are a type of self-balancing binary search tree that maintains their height difference (balance factor) between left and right subtrees within a certain range. This self-balancing 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:

1. Find the in-order successor (the smallest node in the right subtree, which is 13).
2. Replace the value of node 12 with the value of its in-order successor (13).
3. Delete the in-order 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:

1. Perform a regular binary search tree delete operation.
2. Update the height of the current node.
3. Check the balance factor to determine if the tree has become unbalanced.
4. 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

1. The pseudocode outlines the process of deleting a node from an AVL tree while ensuring that the tree remains balanced.
2. The deleteNode function is recursive and follows the steps described earlier.
3. It first performs a standard BST delete operation.
4. Then it updates the height of the current node and checks the balance factor.
5. 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.