AVL insertion on a tree confusion

Question

I am getting a little confused with how insertion on an AVL tree works. I know that the tree must always be balanced at all times. When I try to insert a 21 below the balance needs to be recalculated. If someone could explain to me how this is done I would greatly appreciate it. Thanks!

    BEFORE INSERTING 21                          
           16
           /\
          9  30
         /   / \
        4   23 34
           / \ 
          20 26 


     AFTER INSERTING 21
           16
           /\
          9  30
         /   / \
        4   23 34
           / \ 
          20 26 
           \
           21 

Answer 1

You need to rotate at the level where there is more than one height difference between the left subtree and the right subtree.

BEFORE INSERTING 21                          
       16
       /\
      9  30
     /   / \
    4   23 34
       / \ 
      20 26 


AFTER INSERTING 21
       16
       /\
      9  30
     /   / \
    4   23 34
       / \ 
      20 26 
       \
       21 

Height difference of 2 at node 30. So rotate right at node 30.

AFTER ROTATION
       16
       / \
      9   23
     /   /  \
    4   20  30
         \  / \
         21 26 34

There are single and double rotations. In your case a single rotation is enough. But this might not be the case every time. See how rotations work.