Tree rotation

From Free net 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.

Examples

The tree

       D
      / \
     /   \
    B     E
   / \
  A   C

can be rotated to look like

     B
    / \
   /   \
  A     D
       / \ 
      C   E 

This is called a right rotation. Going from the second tree to the first would be a left rotation.

If we write our tree nodes as (left subtree, node value, right subtree), then the first structure is ((A, B, C), D, E), and the second is (A, B, (C, D, E)), and computing one from the other is very simple. The following is example Python code that performs that computation:

def right_rotation(treenode):
    left, D, E = treenode
    A, B, C = left
    return (A, B, (C, D, E))

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 can be written as compositions of left and 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.

References

• Java applets demonstrating tree rotations (dynamic)
• Java applets demonstrating tree rotations