Debugging AVL Tree Deletion: Unbalanced Node Not on Deletion Path

Question

I'm working on implementing an AVL tree in C++, and I've run into a situation where, after deleting a node and rebalancing the tree, a node not directly on the path from the deleted node to the root becomes unbalanced. I've walked through my deletion and rebalancing algorithm, but I can't seem to identify the problem.

Here's the initial AVL tree state before any operations:

I want to delete the node with the value "914". According to my algorithm, I proceed with the deletion and then perform the necessary rotations to rebalance the tree. However, after the deletion and rebalancing process, I end up with an unbalanced node that wasn't a direct ancestor of the deleted node.

Here's the tree after deletion and rebalancing operations:

1. after deleting:

2. balancing the node that replaces the deleted one:

3. balancing the root - part a:

4. balancing the root - part b:

My algorithm updates the heights and balances after every rotation, and it seems to follow the correct AVL deletion process. However, it ends up with node "381" being unbalanced, and I can't figure out why.

Answer 1

The error is in the first rotation you apply to balance the root (part a): this rotation is not called for. It would only be needed if the left child of the root would be right heavy. But it isn't. And so you shouldn't perform that "part a", but only apply a single rotation at the root to the right.

Here is the whole sequence from the starting point:

             ___720___
            /         \
       ___381__       914
      /        \      / \
   _169_       459  735 915
  /     \      / \    \
159     272  426 561  783
  \     / \      / \
  165 218 286  537 717

After deletion of 914

             ___720___
            /         \
       ___381__       915
      /        \      /
   _169_       459  735
  /     \      / \    \
159     272  426 561  783
  \     / \      / \
  165 218 286  537 717

Node 915 is not balanced: as its left child is right-heavy, we need a double rotation (first 735 to the left, then 915 to the right):

             ___720___
            /         \
       ___381__       783
      /        \      / \
   _169_       459  735 915 
  /     \      / \
159     272  426 561
  \     / \      / \
  165 218 286  537 717

Node 720 is not balanced. But here the left child of 720 is not right-heavy, so we need a single rotation of 720 to the right:

       ______381_____
      /              \
   _169_            _720_
  /     \          /     \
159     272      459     783 
  \     / \      / \     / \
  165 218 286  426 561 735 915 
                   / \
                 537 717

And now the tree is balanced.