14.2 Rotations |

Let's consider how rotations work in PBSTs. Here's the usual illustration of a rotation:

As we move from the left side to the right side, rotating right at
*Y*, the parents of up to three nodes change. In any case, *Y*'s
former parent becomes *X*'s new parent and *X* becomes *Y*'s new
parent. In addition, if *b* is not an empty subtree, then the parent
of subtree *b*'s root node becomes *Y*. Moving from right to left,
the situation is reversed.

**See also:**
[Cormen 1990], section 14.2.

**Exercises:**

**1.** Write functions for right and left rotations in BSTs with parent
pointers, analogous to those for plain BSTs developed in
Exercise 4.3-2.
[answer]