AVL Tree Deletion Tutorial

AVL tree is a height-balanced Binary Search Tree(BST) with best and worst-case height as O(log N). In AVL tree the difference of height of left and right subtree (BalanceFactor) is always 1 or 0 or -1.

In the previous post, we have already discussed the AVL tree insertion. In this post, we will follow a similar approach for deletion.

AVL Tree Deletion

Deletion in an AVL is similar to deletion in BST except after any deletion the tree should be balanced i.e, the BalanceFactor ∈ {1, 0, -1}. In case this property is violated we will do rotations to rebalance the tree.

Rotation in an AVL tree

In an AVL tree, we have to do Left or Right rotation for rebalancing a tree in case of an imbalance. Below is the representation of how the tree structure will change after a rotation.

Let T1, T2 are subtrees of the tree rooted with x
and x & T3 are subtree of tree rooted with y 
           
     y                               x
    / \     Right Rotation          /  \
   x   T3   - - - - - - - >        T1   y 
  / \       < - - - - - - -            / \
 T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the 
following order 
 keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

Various cases in which rotations are done

1. Left-Left case

In the following tree, x is left child of y and y is the left child of z, hence to balance this tree we have to right rotate this tree around the node z.

2. Left-Right Case

In the following tree, x is the right child of y, and y is the left child of z, hence to balance this tree first we have to left rotate the tree around the node y and then right rotate the resulting tree around the node z.

3. Right-Right Case

In the following tree, x is the right child of y, and y is the right child of z, hence to balance this tree we have to left rotate this tree around the node z.

4. Right-Left Rotation

In the following tree, x is the left child of y, and y is the right child of z, hence to balance this tree first we have to right rotate the tree around the node y and then left rotate the resulting tree around the node z.

Steps for Deletion

Suppose we are given an AVL tree T and N is the new node to be inserted.

1. Perform a standard BST deletion of node N in the AVL tree T.
2. Starting from node N, traverse up until the first unbalanced node is not found. Let z be the first unbalanced node, y be the child of z that comes on the path from p to z and x be the grandchild of z that comes on the path from p to z.
3. Rebalance the tree by performing suitable rotations on the subtree (rooted at z). There can be the following 4 possible cases and after choosing what case is it, we have to do appropriate rotation explained above.
   1. Left-Left Case – y is left child of z and x is left child of y
   2. Left-Right Case – y is left child of z and x is the right child of y
   3. Right-Right Case – y is the right child of z and x is the right child of y
   4. Right-Left Case – y is the right child of z and x is left child of y

Note: Unlike insertion in case of deletion we not only need to re-balance the subtree where the first imbalance has occurred but also its unbalanced ancestors too.

Example

Let’s understand the steps of doing deletion using the following example. Given an AVL tree with nodes 56, 35, 66, 15, 40, 60, 75, 10, 20, 47, 80, 25 (in level order) as shown below, delete the node 60 from the given AVL Tree.

Delete 60 

Now, node 56 (parent of node 66) has also become unbalanced. Hence we have to rebalance it too. (Property – Unlike insertion in case of deletion we not only need to re-balance the subtree where the first imbalance has occurred but also its unbalanced ancestors too)

Time Complexity

The time complexity of deletion in an AVL tree is also O(log N), where N, is the number of nodes in the tree. The important thing to remember is that the rotation operations (left and right rotate) take constant time O(1) as only a few pointers are being changed there. Updating the height and getting the balance factor also takes constant time.