Tree rotation

A local change of root and child pointers that preserves inorder order. A right rotation promotes a left child, moves that child's right subtree to the old root's left position, and makes the old root its right child. The five inorder pieces remain in the same order; a left rotation reverses this transformation. Rotation does not by itself require search-tree key ordering.

For old root $y$ with left child $x$ and untouched subtrees $A,B,C$, change the shape from $((A,x,B),y,C)$ to $(A,x,(B,y,C))$. Both have inorder sequence $A,x,B,y,C$. In a destructive traversal that only rotates at the current root, this transformation extends the right spine by one node and decreases the left-size potential by one.