AVL Double Rotation
Channel: Jonathan Anderson
Date: 2018-07-06

In the last video we saw how a single rotation can help an AVL tree maintain its balance property when we insert new outer nodes. However, a single rotation isn't always enough to maintain the balance of an AVL tree.

When we violate the AVL balance property by insertion of an _inner_ node, that is, the right child of a left node or the left child of a right node, a single rotation doesn't actually fix anything. If we follow the rotation rules from the last video, we will end up grafting the new node onto a node (which used to be the pre-rotation subtree root) at the same depth in the subtree. A left-right node becomes a right-left node, but it remains an inner node at the same depth!

To fix this situation, we first need to arrange for our subtree to be too deep in an outer node rather than an inner one. Once we have that situation, we'll be able to fix it through the kind of rotation that we saw in the last video. So how do convert a tree with a too-deep inner child into one with a too-deep outer child? Through a rotation!

Here we see an inner node insertion that causes a subtree to go out of balance. We can't directly fix this situation, but we can put ourselves one step closer to solving the problem. If we perform a left rotation on the subtree rooted at 4, we will still end up with the tree rooted at 17 being out of balance, but now it's out of balance thanks to an outer node rather than an inner node. This is a problem we know how to solve! We can fix this by applying a right rotation to the tree rooted at 17, and we end up with a balanced tree once again. So: when we are out of balance due to going too deep with an _inner_ child, we need to perform a **double rotation**: once to get into a situation with a too-deep _outer_ child and once more to rebalance the tree. **Question:** what is the complexity of performing this double-rebalancing in terms of the number of nodes in the tree?

So now we've seen what an AVL tree is and how it maintains its balance through all sorts of insertion operations. We may also need to rebalance -- using exactly the same single- or double-rotation techniques -- when we remove a node that throws us out of balance. Take a few moments now to practice visualizing these kinds of rotations using VisuAlgo.net. Just as before, start by planning a tree that you want to insert into or remove from, then predict what the effect will be, then use the visualization tool to confirm your hypotheses. Then we'll practice writing the code in class!