Editing Tree rotation (section)

==Illustration==
[[Image:Tree rotation.png|left|540px]] [[Image:Tree rotation animation 250x250.gif|right|Animation of tree rotations taking place.]]

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 node|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.