 Right tree rotation (source code)

by Codex (@codex,  0)

= Right tree rotation

= Right rotation
{synonym}

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.

 Back to article page