How to balance a dangling node in an AVL tree

I have a sequence of numbers that are supposed to be placed into an AVL tree:

50, 22, 80, 70, 75, 73

I'm not sure where 73 goes. On my understanding the first balance happens when 75 becomes the right child of 70:

  50
 /  \
22   80
    /
  70
    \
    75 

Thus, 80 is the "unbalanced" node and 70 is the heavy left child. So 70 moves to the left and 80 moves to the right, somehow, like this:

      50
     /  \
    22   75
        /  \
       70   80

Adding 73, we become unbalanced yet again:

      50
     /  \
    22   75
        /  \
       70   80
         \
          73

How do I balance this? I can't just put 73 between 75 and 70, can I?

1 answer

  • answered 2018-05-16 05:26 Romeo Sierra

    What is being done to retain the AVL Property of trees is known as tree rotations. When it comes to AVL trees, we take a special attribute of nodes, in to consideration, named Balance Factor, which is the magnitude of the difference of the heights of the left and right sub trees for any node. For example, when 73 is added to your tree, balance factor for node 50 (written as BF(50) from now on) will become

    BF(50) = | HeightLeft(50) - HeightRight(50) |
           = | 1 - 3 |
           = 2
    

    For a binary search tree to be an AVL tree, for each node n in the tree BF(n) should always be at most 1. Which means, once 73 is added, BF(50) becomes 2, hence the tree becomes unbalanced in terms of an AVL tree. Readjusting the tree to obtain the AVL property is done by performing rotations in the tree.

    At once 73 is added, it would look like follows.

          50
         /  \
        22   75
            /  \
           70   80
             \
              73
    

    Rotate left from 73, will give the follows.

          50
         /  \
        22   75
            /  \
           73   80
          /  
         70  
    

    Another rotation to right at 73 will give the follows.

          50
         /  \
        22   73
            /  \
           70   75
                 \
                  80
    

    Third rotation to left at 73 will give follows.

          73
         /  \
        50   75
       /  \    \
      22   70   80
    

    That's it. Now we have a balanced tree.

    You could interpret the rotations as any of

    • A left rotation followed by right-left double rotation
    • A left-right double rotation followed by a left rotation

    Read this for further knowledge on tree rotations to obtain balance.