Tree rotationsEdit

A tree rotation, used in such data structures as AVL trees and Red-Black trees (so-called "self-balancing" binary search trees), can be used to change the depth of a pair of subtrees while preserving the older that the elements would be visited using an in-order traversal.

Example of a right rotation:

Before:            After:
-----------------------------
    D                 B
   / \               / \
  B   E    -->      A   D
 / \                   / \
A   C                 C   E

Note the traversal order (A, B, C, D, E) of an in-order depth-first search is the same for both trees. Likewise, if this is a binary search tree, the invariant — that the left subtree contains only nodes less than or equal to the subtree’s root, and the right subtree contains only nodes greater than or equal to the subtree’s root — is maintained.

The pseudo code shows that rotation is a constant time (O(1)) operation:

# right rotation:
pivot = root.left_child             # ie. the "pivot" (the new root) will be B
root.left_child = pivot.right_child # ie. C
pivot.right_child = root            # ie. root gets transplanted beneath pivot
root = pivot                        # pivot becomes new root

# left rotation (reversing the process):
pivot = root.right_child            # this time D is the pivot
root.right_child = pivot.left_child # ie. C
pivot.left_child = root             # ie. root gets transplanted
root = pivot