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]