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 node up in the tree and one node 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.
There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root's place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.
Read more about Tree Rotation: Illustration, Detailed Illustration, Inorder Invariance, Rotations For Rebalancing, Rotation Distance
Famous quotes containing the words tree and/or rotation:
“What I want to say, Linda,
is that there is nothing in your body that lies.
All that is new is telling the truth.
I’m here, that somebody else,
an old tree in the background.”
—Anne Sexton (1928–1974)
“The lazy manage to keep up with the earth’s rotation just as well as the industrious.”
—Mason Cooley (b. 1927)