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.
[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).
[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 goes 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 X:
Let Y be X's right child. Set Y to be the new root. Set X's right child to be Y's left child. Set Y's left child to be X.
Right Rotation of node X:
Let Y be X's left child. Set Y to be the new root. Set X's left child to be Y's right child. Set Y's right child to be X.
All other connections are left as-is.
There are also "double left" and "double right" rotations, which are simply compositions of two left or two right rotations.
Tree rotations are used in a number of tree data structures such as AVL trees, red-black trees, and splay trees. 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.
