Tree rotation

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.

(“Tree Rotation” 2022)

(“Tree Rotation” 2022)

(“Tree Rotation” 2022)

Left tree rotation

Before	After

1. \(\text{x}\texttt{[right]} := \text{y}\texttt{[left]} \; (\beta)\)
2. \(\text{y}\texttt{[left]} := \text{x}\)
3. \(\text{x}\texttt{[parent][?]} := \text{y}\)

Right tree rotation

Before	After

1. \(\text{y}\texttt{[left]} := \text{x}\texttt{[right]} \; (\beta)\)
2. \(\text{x}\texttt{[right]} := \text{y}\)
3. \(\text{y}\texttt{[parent][?]} := \text{x}\)

Bibliography

Backlinks

• Red-black tree