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:
See also: [Cormen 1990], section 14.2; [Sedgewick 1998], section 12.8.
1. For each of the binary search trees below, perform a right rotation at node 4.
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?