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]