Structural Rotation: Definition
Consider these numbers: $3, 5, 7$. The following are valid binary search trees made up of the given numbers. However, only one is "balanced."
![](/img/19/avl01.png)
![](/img/19/avl02.png)
![](/img/19/avl03.png)
![](/img/19/avl04.png)
![](/img/19/avl05.png)
The four unbalanced trees can be transformed to the balanced one using structural rotation. (Notice the balanced one can be generated from the sequence $5, 3, 7$ or $5, 7, 3$.)
A structural rotation is an operation on a binary tree that changes the tree's structure without affecting the order of the elements (as read in by an in-order traversal).
A structural rotation is often employed to balance two branches of different depths.
In a structural rotation, one node is shifted up, another is shifted down, and some of the remaining nodes may be shifted to ensure the tree is still a binary tree (each node only has two branches).
Structural rotations change the height of the tree by moving up larger subtrees.