4.3 Rotations

Soon we'll jump right in and start implementing the table functions for BSTs. But before that, there's one more topic to discuss, because they'll keep coming up from time to time throughout the rest of the book. This topic is the concept of a rotation (see rotation). A rotation is a simple transformation of a binary tree that looks like this:

In this diagram, X and Y represent nodes and a, b, and c are arbitrary binary trees that may be empty. A rotation that changes a binary tree of the form shown on the left to the form shown on the right is called a right rotation (see right rotation) on Y. Going the other way, it is a left rotation (see left rotation) on X.

This figure also introduces new graphical conventions. First, the line leading vertically down to the root explicitly shows that the BST may be a subtree of a larger tree. Also, the use of both uppercase and lowercase letters emphasizes the distinction between individual nodes and subtrees: uppercase letters are nodes, lowercase letters represent (possibly empty) subtrees.

A rotation changes the local structure of a binary tree without changing its ordering as seen through inorder traversal. That's a subtle statement, so let's dissect it bit by bit. Rotations have the following properties:

Rotations change the structure of a binary tree.

In particular, rotations can often, depending on the tree's shape, be used to change the height of a part of a binary tree.

Rotations change the local structure of a binary tree.

Any given rotation only affects the node rotated and its immediate children. The node's ancestors and its children's children are unchanged.

Rotations do not change the ordering of a binary tree.

If a binary tree is a binary search tree before a rotation, it is a binary search tree after a rotation. So, we can safely use rotations to rearrange a BST-based structure, without concerns about upsetting its ordering.

See also:  [Cormen 1990], section 14.2; [Sedgewick 1998], section 12.8.

Exercises:

1. For each of the binary search trees below, perform a right rotation at node 4.

[answer]

2. Write a pair of functions, one to perform a right rotation at a given BST node, one to perform a left rotation. What should be the type of the functions' parameter? [answer]