How do you know where to perform rotations in an AVL tree?

Question

So I'm self teaching AVL trees and I understand the basic idea behind it, but I just want to make sure my intuition of actually implementing it is valid:

I'll examine it with the left rotation-

So, the following situation is simple:

      8      / \     7   10    /   6  / 3 

When we add the 3, the tree rebalances itself to:

    8    / \   6   10  / \ 3   7 

But is the rotation based on the addition of the 3 or the imbalance of the subtree rooted at 7? Is it even based on the imbalance of the tree rooted at 8?

The following example is where things get a bit hairy, in my opinion:

      9      / \     7   10    / \   6   8  / 3 

So, in this case, the subtree at 7 is fine when the 3 is added, so that subtree doesn't need to rotate. However, the tree at 9 is imbalanced with the addition of 3, so we base the rotation at 9. We get:

      7      / \     6   9    /   / \   3   8   10 

So in writing my code, which I will quite soon, would the following code, starting from small subtrees working up to bigger subtrees do the trick?

pseudocode:

function balanceTree(Node n){    if (n is not null){      balanceTree(n.rightchild);     balanceTree(n.leftchild);   }    if (abs(balanceFactor(n))>1){      rotateAsNeeded(n);// rotate based on balance factor    }  } 

Thanks in advance!

Answer 1

The pseudocode that you've posted will correctly balance a tree. That said, it is too inefficient to be practical - notice that you're recursively exploring the entire tree trying to do rebalancing operations, which will make all insertions and deletions take O(n) time, eating away all the efficiency gains of having a balanced tree.

The idea behind AVL trees is that globally rebalancing the tree can be done by iteratively applying local rotations. In other words, when you do an insertion or deletion and need to do tree rotations, those rotations won't appear in random spots in the tree. They'll always appear along the access path you took when inserting or deleting the node.

For example, you were curious about inserting the value 3 into this tree:

      9      / \     7   10    / \   6   8 

Let's start off by writing out the difference in balance factors associated with each node (it's critical that AVL tree nodes store this information, since it's what makes it possible to do insertions and deletions efficiently):

           9(+1)          /       \        7 (0)    10 (0)       / \   6(0)   8(0) 

So now let's see what happens when we insert 3. This places the 3 here:

           9(+1?)           /       \         7 (0?)    10 (0)        /   \    6(0?)   8(0)    /  3(0) 

Notice that I've marked all nodes on the access path with a ?, since we're no longer sure what their balance factors are. Since we inserted a new child for 6, this changes the balance factor for the 6 node to +1:

           9(+1?)           /       \         7 (0?)    10 (0)        /   \    6(+1)   8(0)    /  3(0) 

Similarly, the left subtree of 7 grew in height, so its balance factor should be incremented:

           9(+1?)           /       \         7 (+1)    10 (0)        /   \    6(+1)   8(0)    /  3(0) 

Finally, 9's left subtree grew by one, which gives this:

           9(+2!)           /       \         7 (+1)    10 (0)        /   \    6(+1)   8(0)    /  3(0) 

And here we find that 9 has a balance factor of +2, which means that we need to do a rotation. Consulting Wikipedia's great table of all AVL tree rotations, we can see that we're in the case where we have a balance factor of +2 where the left child has a balance factor of +1. This means that we do a right rotation and pull the 7 above the 9, as shown here:

        7(0)        /   \    6(+1)     9(0)    /       /   \  3(0)    8(0)   10 (0) 

Et voilà! The tree is now balanced.

Notice that when we did this fixup procedure, we didn't have to look over the entire tree. Instead, all we needed to do was look along the access path and check each node there. Typically, when implementing an AVL tree, your insertion procedure will do the following:

• If the tree is null:
  • Insert the node with balance factor 0.
  • Return that the tree height has increased by 1.
• Otherwise:
  • If the value to insert matches the current node, do nothing.
  • Otherwise, recursively insert the node into the proper subtree and get the amount that the tree height has changed by.
  • Update the balance factor of this node based on the amount that the subtree height changed.
  • If this mandates a series of rotations, perform them.
  • Return the resulting change in the height of this tree.

Since all these operations are local, the total work done is based purely on the length of the access path, which in this case is O(log n) because AVL trees are always balanced.

Hope this helps!

---

PS: Your initial example was this tree:

      8      / \     7   10    /   6  / 3 

Note that this tree isn't actually a legal AVL tree, since the balance factor of the root node is +2. If you consistently maintain tree balance using the AVL algorithm, you will never encounter this case.