# 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
```