11.3 Rotations

We will use rotations in right-threaded trees in the same way as for other kinds of trees that we have already examined. As always, a generic rotation looks like this:

On the left side of this diagram, a may be an empty subtree and b and c may be threads. On the right side, a and b may be empty subtrees and c may be a thread. If none of them in fact represent actual nodes, then we end up with the following pathological case:

Notice the asymmetry here: in a right rotation the right thread from X to Y becomes a null left child of Y, but in a left rotation this is reversed and a null subtree b becomes a right thread from X to Y. Contrast this to the correponding rotation in a threaded tree (see TBST Rotations), where either way the same kind of change occurs: the thread from X to Y, or vice versa, simply reverses direction.

As with other kinds of rotations we've seen, there is no need to make any changes in subtrees of a, b, or c, because of rotations' locality and order-preserving properties (see BST Rotations). In particular, nodes a and c, if they exist, need no adjustments, as implied by the diagram above, which shows no changes to these subtrees on opposite sides.

Exercises:

1. Write functions for right and left rotations in right-threaded BSTs, analogous to those for unthreaded BSTs developed in Exercise 4.3-2. [answer]