In discrete mathematics, tree rotation is an operation on a Binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one [Vertex] up in the tree and one [Vertex] down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.

## Left tree rotation

Before | After |
---|---|

- \(\text{x}\texttt{[right]} := \text{y}\texttt{[left]} \; (\beta)\)
- \(\text{y}\texttt{[left]} := \text{x}\)
- \(\text{x}\texttt{[parent][?]} := \text{y}\)

## Right tree rotation

Before | After |
---|---|

- \(\text{y}\texttt{[left]} := \text{x}\texttt{[right]} \; (\beta)\)
- \(\text{x}\texttt{[right]} := \text{y}\)
- \(\text{y}\texttt{[parent][?]} := \text{x}\)

## References

“Tree Rotation.” 2022.

*Wikipedia*, July. https://en.wikipedia.org/w/index.php?title=Tree_rotation&oldid=1099813959.