What to do when the AVL tree is unbalanced on the right node but there are 2 children?

Question

I'm learning about AVL trees in class. Then I try to create one tree and then delete the nodes. But I don't know what method to choose to balance the tree correctly.

Ex. 22,13,19,20,50,18,33,49
Then subtract 20.

This is my tree with 20 removed, but not balanced at 22, but I'm not going to balance it using SLL or DRL methods.

    19  
 /      \  
13       22  <-----here  
\          \ 
18         49  
          /  \ 
         33  50

I want to know how to adjust the balance. Please give me some advice. Thank you.

Answer 1

Indeed, if you insert those values in that order into an empty AVL tree, and then delete value 20, you get into that situation:

       __19__  
      /      \  
    13        22  <-----    
      \         \ 
       18        49  
                /  \ 
              33    50

While rebalancing you always start at the current node where the deletion took place, as this is the lowest point in the tree that could have an imbalance.

The principle is that you solve that imbalance, and then check the ancestors, working your way up the tree towards the root until there is no more imbalance. This is called retracing.

Although one could argue that a rotation at a higher level could sometimes also work, that is not how it is done.

In this case the subtree rooted at 22 is not in balance.

To restore the balance, we need a simple rotation to the left (i.e. anti-clockwise) at node 22, lifting up its right child.

See Wikipedia on tree rotations which has this image for illustrating simple rotations:

In your case you'll want to rotate left, so we start at the right side of the above image, with P=22, Q=49, B=33, and after the rotation you'll get the left-side situation:

       __19__  
      /      \  
    13        49  <----- after rotation-to-left
      \      /  \ 
       18  22    50  
             \ 
              33

And now the node 19 would be checked (as we work upwards), but its balance factor is fine, so no more action is needed.