Екілік ағаштардағы бұрылыс операциясы және жапырақтар тәртібінің сақталуы

A local change in a binary tree that preserves leaf order

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 rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node.

The right rotation operation as shown in the adjacent image is performed with Q as the root and hence is a right rotation on, or rooted at, Q. This operation results in a rotation of the tree in the clockwise direction. The inverse operation is the left rotation, which results in a movement in a counter clockwise direction (the left rotation shown above is rooted at P). The key to understanding how a rotation functions is to understand its constraints. In particular the order of the leaves of the tree (when read left to right for example) cannot change (another way to think of it is that the order that the leaves would be visited in an in order traversal must be the same after the operation as before). Another constraint is the main property of a binary search tree, namely that all nodes in the right subtree are greater than the parent and all nodes in the left subtree are less than the parent. Notice that the right child of a left child of the root of a sub tree (for example node B in the diagram for the tree rooted at Q) can become the left child of the root, that itself becomes the right child of the "new" root in the rotated sub tree, without violating either of those constraints. As seen in the diagram, the order of the leaves doesn't change. The opposite operation also preserves the order and is the second kind of rotation. Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables that can be compared to each other. The alphabetic characters to the left are used as placeholders for these variables. In the animation to the right, capital alphabetic characters are used as variable placeholders while lowercase Greek letters are placeholders for an entire set of variables. The circles represent individual nodes and the triangles represent subtrees. Each subtree could be empty, consist of a single node, or consist of any number of nodes.

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.

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, though several variants of the rotation distance problem admit polynomial time algorithms. 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 this far apart as soon as n is sufficiently large. Lionel Pournin showed that, in fact, such pairs exist whenever n ≥ 11.