AVL tree | Deletion

Write a program to delete given key from the given AVL tree while maintaining height balance of the AVL tree. You might want to check out this previous post which covers the basics of AVL trees.


Question Asked in

Google, Amazon


Video coming soon!



Subscribe for more updates


Algorithm/Insights

We will try to understand this algorithm using an example but before that let's go over the major steps of this algorithm. Note that this algorithm is a bottom-up algorithm and hence height restoration of the tree proceeds from leaves to root.

This algorithm is basically a modification of the usual BST deletion algorithm. The steps of this algorithm are -
1. Use general BST deletion algorithm to delete given key from the AVL tree.
2. After deletion, update the height of the current node of the AVL tree.
3. Now check the 'balance' at the current node by getting the difference of height of left sub-tree and height of right sub-tree.
3a. If 'balance' > 1 then that means the height of the left sub-tree is greater than the height of the right sub-tree. This indicates left-left or left-right case(discussed in the previous post). To confirm if this is left-left or left-right case, we check the balance of left sub-tree of current node. If it greater than 0 then that confirms left-left case, if it less than 0 then that confirms left-right case. If it is equal to 0, then this we can either consider this as a left-left case or as a left-right case. In this implementation, we consider this as left-left case for efficiency. For left-left case, we do a right rotation at the current node. For the left-right case, we do a left rotation at left child of current node followed by a right rotation at the current node itself.

3b. If 'balance' < -1 then that means the height of the right sub-tree is greater than the height of the left sub-tree. This indicates right-right or right-left case(discussed in the previous post). In this case, if balance of right sub-tree of current node is less than 0 then this confirms right-right case, if it is greater than 0 then this confirms right-left case. If it is equal to 0, then we can either consider this as a right-right case or a right-left case. In this implementation, we will consider this as a right-right case. In right-right case, we do a left rotation at the current node. In right-left case, we do a right rotation at the right child of current node followed by left rotation at the current node itself.


Example walk-through: Let's delete key sequence [6,5,4] from the below AVL tree and see how the height balance is maintained throughout.


Delete key 6:


Delete key 5:


Delete key 4:

  
At this point, there is a height imbalance at node 3 with the left-left case. We do a right rotation at node 3.


As you can confirm this tree satisfies height balance property for AVL tree.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.LinkedList;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * AVL Tree deletion algorithm with required rotations for balancing.
 * @author Nilesh
 */

public class AVLTree 
{
    
    private class QueueNode
    {
        AVLTreeNode treeNode;
        int level;
        
        QueueNode(AVLTreeNode treeNode, int level)
        {
            this.treeNode = treeNode;
            this.level = level;
        }
    }
    
    private class AVLTreeNode 
    {
        int data;
        AVLTreeNode left;
        AVLTreeNode right;
        int height;
        
        AVLTreeNode(int data)
        {
            this.data = data;
            this.height = 1;
        }
    }
    
    AVLTreeNode root;
    
    // default value for root node is 9
    AVLTree()
    {
        this.root = new AVLTreeNode(9);
    }
    
    AVLTree(int rootValue)
    {
        this.root = new AVLTreeNode(rootValue);
    }
    
    int getHeight(AVLTreeNode node)
    {
        if (node == null)
            return 0;
        
        return node.height;
    }
    
    void updateHeight(AVLTreeNode node)
    {
        if (node == null) return;
        
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
    
    
    AVLTreeNode rotateRight(AVLTreeNode node)
    {
        if (node == null) return node;
        
        AVLTreeNode beta  = node.left;
        
        AVLTreeNode t2  = beta.right;
        
        beta.right = node;
        node.left = t2;
        
        // we first need to update the height of node because height of beta uses height of node
        updateHeight(node);
        
        // now we update height of beta
        updateHeight(beta);
        
        return beta;
    }
    
    
    AVLTreeNode rotateLeft(AVLTreeNode node)
    {
        if (node == null) return node;
        
        AVLTreeNode beta  = node.right;
        AVLTreeNode t2  = beta.left;
        
        beta.left = node;
        node.right = t2;
        
        // we first need to update the height of node because height of beta uses height of node
        updateHeight(node);
        
        // now we update height of beta
        updateHeight(beta);
        
        return beta;
    }
    
    
    int getBalance(AVLTreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        int balance;
        
        balance = getHeight(node.left) - getHeight(node.right);
        
        return balance;
    }
    
    
    int getMinValue(AVLTreeNode node)
    {
        // though this case should not be hit ever for the usecase this function is employed for
        if (node == null) return Integer.MIN_VALUE;
        
        // if this is the left-most node
        if (node.left == null) return node.data;
        
        return getMinValue(node.left);
    }
    
    
    private AVLTreeNode delete(AVLTreeNode node, int key)
    {
        // if empty tree 
        if (node == null) return null;
        
        if (key < node.data)
        {
            node.left = delete(node.left, key);
        }
        else if (key > node.data)
        {
            node.right = delete(node.right, key);
        }
        
        else // key to be deleted is equal to node data 
        {
            // one child/no child case
            if (node.left == null)
            {
                node = node.right;
            }
            else if (node.right == null)
            {
                node = node.left;
            }
            
            // two children case
            // copy value of inorder successor into current node and delete inorder successor
            // since right sub-tree would be modified, update node.right
            else
            {
                int inorderSuccessorValue = getMinValue(node.right);
                node.data = inorderSuccessorValue;
                node.right = delete(node.right, inorderSuccessorValue);
            }
        }

        // if there was only one node in the tree which got deleted above return null 
        if (node == null)
        {
            return null;
        }
        
        // update the height of the node
        updateHeight(node);
        
        // check the balance at this node and perform rotations accordingly
        int balance = getBalance(node);
        
        if (balance > 1) // indicates either left-left or left-right case
        {
            if (getBalance(node.left) >= 0) // confirms left-left case
            {
                node = rotateRight(node);
            }
            else // confirms left-right case
            {
                node.left = rotateLeft(node.left);
                node = rotateRight(node);
            }
        }
        
        else if (balance < -1) // indicates either right-right or right-left case
        {
            if (getBalance(node.right) <= 0) // confirms right-right case
            {
                node = rotateLeft(node);
            }
            else // confirms right-left case
            {
                node.right = rotateRight(node.right);
                node = rotateLeft(node);
            }
        }
        return node;
    }
    
    
    private AVLTreeNode insert(AVLTreeNode node, int key)
    {
        // do usual BST insertion first
        if (node == null)
        {
            return new AVLTreeNode(key);
        }
        
        if (key < node.data)
        {
            node.left = insert(node.left, key);
        }
        else if (key > node.data)
        {
            node.right = insert(node.right, key);
        }
        else
        {
            return node;
        }
        
        // now update the height of the node
        updateHeight(node);
        
        // check the balance at this node and perform rotations accordingly
        int balance = getBalance(node);
        
        if (balance > 1) // indicates either left-left or left-right case
        {
            if (key < node.left.data) // confirms left-left case
            {
                node = rotateRight(node);
            }
            else // confirms left-right case
            {
                node.left = rotateLeft(node.left);
                node = rotateRight(node);
            }
        }
        
        else if (balance < -1) // indicates either right-right or right-left case
        {
            if (key > node.right.data) // confirms right-right case
            {
                node = rotateLeft(node);
            }
            else // confirms right-left case
            {
                node.right = rotateRight(node.right);
                node = rotateLeft(node);
            }
        }
        return node;
    }
    
    
    public void insert(int key)
    {
        root = insert(this.root, key);
        return;
    }
    
    
    public void delete(int key)
    {
        root = delete(this.root, key);
        return;
    }
    
    
    public void printTreeLevelOrder()
    {
        if (root == null) return;
        
        LinkedList queue = new LinkedList();
        queue.add(new QueueNode(root, 0));
        
        int maxLevelVisited = -1;
        
        while (!queue.isEmpty())
        {
            QueueNode currentNode = (QueueNode) queue.remove();
            
            if (currentNode.level > maxLevelVisited)
            {
                maxLevelVisited = currentNode.level;
                System.out.print("\nlevel-" + currentNode.level + " nodes: ");
            }
            System.out.print(" " + currentNode.treeNode.data);
            
            if (currentNode.treeNode.left != null)
            {
                queue.add(new QueueNode(currentNode.treeNode.left, currentNode.level + 1));
            }
            
            if (currentNode.treeNode.right != null)
            {
                queue.add(new QueueNode(currentNode.treeNode.right, currentNode.level + 1));
            }
        }
    }
    
    
    public static void main(String[] args)
    {
        AVLTree tree = new AVLTree(0);

        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
        tree.insert(6);
        tree.insert(5);

        System.out.print("AVL tree before deleting any key");
        tree.printTreeLevelOrder();

        tree.delete(1);

        System.out.print("\n\nAVL tree after deleting key with value 1");
        tree.printTreeLevelOrder();
    }
}
		

Order of the Algorithm

Time Complexity is O(logn)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer