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

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 node50
(written asBF(50)
from now on) will becomeBF(50) =  HeightLeft(50)  HeightRight(50)  =  1  3  = 2
For a binary search tree to be an AVL tree, for each node
n
in the treeBF(n)
should always be at most 1. Which means, once73
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 rightleft double rotation
 A leftright double rotation followed by a left rotation
Read this for further knowledge on tree rotations to obtain balance.