How to delete a node from an AVL tree

AVL trees are self-balancing binary search trees. This means that these trees can restore the balance whenever an imbalance is created via the insertion or deletion of a node(s).

This maintenance of balance in an AVL tree allows operations such as insertion, deletion, and searching to run in. $O(log(N))$ time. As a result, it makes them much more efficient than simple binary search trees, which take $O(N)$ time in the worst case.

Delete a node from an AVL tree

Efficiently deleting a node from an AVL tree requires a recursive approach that involves three main steps:

1. Reach the node to be deleted: We first search for a node with the same value as the node to be deleted. If such a node doesn't exist, we can conclude our process as the value to be deleted doesn't exist.

2. Delete the node itself: Once we reach the desired node, we now need to delete it.

3. Rebalance the tree once the node is deleted: This happens once the backtracking starts. Starting from the deleted node's parent, we travel up the tree until the first unbalanced node (with a balance factorThe balance factor of a node is the difference in the height of the left and right sub-tree. The balance factor of every node in the AVL tree should be either +1, 0 or -1. that lies outside the range [-1, 1]) is found. Then, we perform the required rotationsRotations involve switching around positions of nodes in the unbalanced node's sub-tree(s) each time the balance factor is disrupted. on the subtree of this unbalanced node to rebalance it. This is repeated until we reach the root node and the recursion backtracking ends.

Reach the node to be deleted

To delete a node with a value equal to val_to_delete , we first need to search for it. We compare val_to_delete with the value of each node as we proceed down the tree in search of our node to delete.

Note: To learn more about how we search for an element in an AVL tree, refer to this link.

The example below illustrates how the node with a value equal to val_to_delete is found (the current root node during the recursive calls is colored orange):

Once we reach this node, we can get ready to delete it.

Delete the node itself

To delete a node from an AVL tree, we can have three possible scenarios:

• Delete a leaf node.

• Delete a node with just one child.

• Delete a node with two child nodes.

In each case, the node is deleted from an AVL tree the same way it would be deleted from a binary search tree.

The illustration below shows how the deletion happens, continuing the same example from above:

Rebalance the tree once the node is deleted

During backtracking, we check the balance factor of each node. If the balance factor is in the range [-1, 1], we do nothing and allow backtracking to proceed. However, if the node is unbalanced, we need to perform rotation(s) on it to rebalance it.

If the balance factor is 2, this means that the unbalanced node's left subtree is heavier than the right one. Thus, there is either a left-left imbalance or a left-right imbalance. If the balance factor of the unbalanced node's left child is greater than or equal to 1, this narrows it down to a left-left imbalance, and a right rotation needs to be applied to the unbalanced node. Otherwise, the imbalance is left-right, and a left-right rotation needs to be applied.

Similarly, if the balance factor is -2, this means that the unbalanced node's right subtree is heavier than the left one. Thus, there is either a right-right imbalance or a right-left imbalance. If the balance factor of the unbalanced node's right child is less than or equal to 0, this narrows it down to a right-right imbalance, and a left rotation needs to be applied to the unbalanced node. Otherwise, the imbalance is right-left, and a right-left rotation needs to be applied.

This backtracking process is depicted below, continuing the same example above (the current root node during each backtracking step is colored red).

Code example

The lines highlighted in the code below implement a function deleteNode() to delete a node with a particular value from an AVL tree. This function also makes use of balanceTree().

Explanation

We have a function named deleteNode that takes two arguments, root of the tree and the val_to_delete , value to be delete. Let’s see the code.

• Lines 3-6: If the value of the root is NULL or the tree have no value, then the function will return NULL.

• Lines 8-68: If the roots have values, then keep searching and if the node with same value is found, delete the node and adjust the tree accordingly.

  • Lines 11-54: If the value of the node is found, then we have have 4 scenarios.

    • Line 14-18: If the left and right child of the node are NULL, then we can simply delete the node and return NULL.

    • Line 21-26: If the value of the left child is NULL, then we can make a temporary node temp , assign the value of the right child, delete the current node and return the temp variable.

    • Line 29-34: If the value of the right child is NULL, then we can make a temporary node temp , assign the value of the left child, delete the current node and return the temp variable.

    • Line 37-54: If the node have both left and right child elements. We find the smallest value from the right subtree and replace the node with it.

      • Line 40: Declaring a variable min_right_subtree , to save the node with minimum value.

      • Line 41: Save the right subtree in a variable current, to iterate the tree for a minimum value node.

      • Line 42-45: Iterate the current to the left to reach the left-most leaf that holds the minimum value.

      • Line 46-49: Save the node to the min_right_subtree and its value to the root.

      • Line 52: We have replaced the value of the node with the minimum value from the right subtree. Now, we need to delete the node that holds the minimum value. We are calling the deleteNode function and passing the minimum value.

  • Lines 57-68: Search the node with the same value. If the value is less than the root value, then pass the left child of the root and call the deleteNode and vice versa.

  • Lines 71-76: Checks if the tree needs to be balanced after the deletion of the node, if true . Then, it balances the tree.

  • Line 78: If the node is not found, then it returns the root .