A rotation can help to improve the balance of a tree when one subtree is taller than the other. However, there are cases where a single rotation is not enough to restore balance. This happens when the taller subtree itself is unbalanced in the opposite direction.
To see why this is the case, consider a right rotation on the following tree. At the start, it is unbalanced because the left subtree has a height of 2 while the right subtree has a height of 0. After the right rotation, the tree is still unbalanced because the new left subtree has a height of 0 while the new right subtree has a height of 2.
The key to identifying this situation is to notice that the path to the deeper subtree is a “zig-zag” pattern. In our example, we went left from 5 to 3, and then right from 3 to 4. When we have this zig-zag pattern, a single rotation will not be enough to restore balance. Instead, we need to perform two rotations: one on the child node to straighten out the zig-zag, and then one on the original pivot node to complete the balancing.
In this example, we first perform a left rotation on the 3 node. This straightens out the zig-zag by making 4 the new child of 5. Then, we perform a right rotation on the 5 node. This completes the balancing by making 4 the new root of the subtree, with 3 as its left child and 5 as its right child.
We will refer to this sequence of two rotations as a double rotation. The first rotation is performed on the child of the pivot node, and the second rotation is performed on the pivot node itself. The order of the rotations depends on the direction of the zig-zag pattern. In our example, we had a left-right zig-zag, so we performed a left rotation followed by a right rotation. If we had a right-left zig-zag, we would perform a right rotation followed by a left rotation.
The tree in this animation below is out of balance. The left side of the root is deeper than the right side. But a simple right rotation of the root won’t fix it. (Try if you like and then reset the animation.)
The path from the root where we want to perform the rotation is a zig-zag pattern (first it goes left and then it goes right). Fix it by first doing a left rotation of 10 and then a right rotation of 18. Click on a node (or type its value into the text field) to select it, then press Rotate Left or Rotate Right to start the rotation and then > to step through the animation.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
We don’t always have to rotate at the root of the tree. We generally want to perform rotations at the lowest unbalanced node in the tree. This minimizes the amount of restructuring we have to do and helps to keep the tree as balanced as possible.
The tree below can’t be perfectly balanced. But it can be made more balanced at the 10 node. Perform a double rotation to improve the balance at that subtree.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
