Tree rotation

From Wikipedia, the free encyclopedia

A tree rotation is an operation on a binary search 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. They are 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.

1 Illustration
2 Inorder Invariance
3 External Links
4 See also

[edit] Illustration

The right rotation operation as shown in the image above 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 symmetric operation is the left rotation which results in a movement in an anti-clockwise direction (the left rotation shown above is rooted at P).

Assuming this is a binary search tree, as stated above, the elements must be interpreted as variables and not as alphabetic characters.

[edit] Inorder Invariance

The tree rotation renders the inorder traversal of the binary tree invariant. This implies the order of the elements are not affected when a rotation is performed in any part of the tree. Here are the inorder traversals of the trees shown above:

Left tree: ((A, P, B), Q, C)               Right tree: (A, P, (B, Q, C))

Computing one from the other is very simple. The following is example Python code that performs that computation:

def right_rotation(treenode):
    left, Q, C = treenode
    A, P, B = left
    return (A, P, (B, Q, C))

Another way of looking at it is:

Left Rotation of node P:

Let Q be P's right child.
Set Q to be the new root.
Set P's right child to be Q's left child.
Set Q's left child to be P.

Right Rotation of node Q:

Let P be Q's left child.
Set P to be the new root.
Set Q's left child to be P's right child.
Set P's right child to be 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, 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.

[edit] External Links

Java applets demonstrating tree rotations (dynamic)
Java applets demonstrating tree rotations
The AVL Tree Rotations Tutorial (RTF) by John Hargrove

[edit] See also

AVL tree, a tree that is rebalanced as needed upon any element insertion or deletion by rotations, and so is always optimal for searching operations
Red-black tree, a tree that is is bounded in its degree of imbalance and so has reasonable bounds for searching operations and that also guarentees that an insert or deletion can always be performed with a limited number of rotations (two or three).
Splay tree, where a recently accessed element is moved to the top of the tree, reducing subseqent lookups but which may require subseqent rebalancing to maintain performance

Retrieved from "http://en.wikipedia.org../../../t/r/e/Tree_rotation.html"

Category: Trees (structure)