Tree rotation

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. Tree rotations are used to balance some kinds of trees to improve performance.

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.

See AVL tree, Red-Black tree

Reference: [this] page has some excelent (Free) java applets demonstrating tree rotations. (can we add applets to the Wiki?)