Left rotation of node P: Let Q be P's right child. Set P's right child to be Q's left child. [Set Q's left-child's parent to P] Set Q's left child to be P. [Set P's parent to Q] All other connections are left as-is. There are also double rotations, which are combinations of left and right rotations. A double left rotation at X can be defined to be a right rotation at the right child of X followed by a left rotation at X; similarly, a double right rotation at X can be defined to be a left rotation at the left child of X followed by a right rotation at X. Tree rotations are used in a number of tree data structures such as AVL trees, red–black trees, WAVL trees, splay trees, and treaps. They require only constant time because they are local transformations: they only operate on 5 nodes, and need not examine the rest of the tree. Rotations for rebalancing A tree can be rebalanced using rotations. After a rotation, the side of the rotation increases its height by 1 whilst the side opposite the rotation decreases its height similarly. Therefore, one can strategically apply rotations to nodes whose left child and right child differ in height by more than 1. Self-balancing binary search trees apply this operation automatically. A type of tree which uses this rebalancing technique is the AVL tree. Rotation distance The rotation distance between any two binary trees with the same number of nodes is the minimum number of rotations needed to transform one into the other. With this distance, the set of n-node binary trees becomes a metric space: the distance is symmetric, positive when given two different trees, and satisfies the triangle inequality. It is an open problem whether there exists a polynomial time algorithm for calculating rotation distance. Yet, Fordham's algorithm computes a distance in linear time, but only allows 2 kind of rotations : (ab)c = a(bc) and a((bc)d) = a(b(cd)). Fordham's algorithm relies on a classification of nodes into 7 types, and a lookup table is used to find the number of rotations required to transform a node of one type into an other. Daniel Sleator, Robert Tarjan and William Thurston showed that the rotation distance between any two n-node trees (for n ≥ 11) is at most 2n − 6, and that some pairs of trees are