Rearranging BSTs with Rotations
Imagine we have the following trees, a 2–3–4 tree and an equivalent Red–Black tree:
Now imagine inserting 30.
Here is what should happen in the 2–3–4 tree:
On your own, draw a Red–Black tree that is equivalent to this new 2–3–4 tree.
Here is the equivalent red–black tree:
You can see that a bunch of stuff had to happen!
- Some nodes had to change color.
- Some edges needed to be rewired.
This rearranging of the edges actually has a name: tree rotation (in this case, “a right rotation on the node containing 50”).
Rotation is a fundamental operation for rearranging trees and shows up in lots of self-balancing BST structures.
Rotation
We can picture the rotation in a generic binary tree.
There are two main nodes involved: the root of the tree (or subtree) and the node that will become the new root, which is one of the root's children.
Hanging off those two nodes are three subtrees that we need to pay attention to as well.
Here is a visualization of a rotation operation:
Key Ideas
- Rotation preserves the BST property:
- The old root becomes the child on the correct side of the new root.
- The subtree that lies “between” the old root and the new root remains “between” them.
- The subtrees all the way to the left and all the way to the right stay where they are.
- Rotation takes constant time:
- Rotation only involves a few pointer reassignments, no matter how big the tree is.
- So rotation is a safe and cheap way to rearrange a BST.
For quick reference, here is a diagram of both left- and right-rotation operations:
(When logged in, completion status appears here.)