Skip to content

13.2 Rotations

13.2-1

Write pseudocode for $\text{RIGHT-ROTATE}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
RIGHT-ROTATE(T, y)
    x = y.left
    y.left = x.right
    if x.right != T.nil
        x.right.p = y
    x.p = y.p
    if y.p == T.nil
        T.root = x
    else if y == y.p.right
        y.p.right = x
    else y.p.left = x
    x.right = y
    y.p = x

13.2-2

Argue that in every $n$-node binary search tree, there are exactly $n - 1$ possible rotations.

Every node can rotate with its parent, only the root does not have a parent, therefore there are $n - 1$ possible rotations.

13.2-3

Let $a$, $b$, and $c$ be arbitrary nodes in subtrees $\alpha$, $\beta$, and $\gamma$, respectively, in the left tree of Figure 13.2. How do the depths of $a$, $b$, and $c$ change when a left rotation is performed on node $x$ in the figure?

  • $a$: increase by $1$.
  • $b$: unchanged.
  • $c$: decrease by $1$.

13.2-4

Show that any arbitrary $n$-node binary search tree can be transformed into any other arbitrary $n$-node binary search tree using $O(n)$ rotations. ($\textit{Hint:}$ First show that at most $n - 1$ right rotations suffice to transform the tree into a right-going chain.)

Since the exercise asks about binary search trees rather than the more specific redblack trees, we assume here that leaves are full-fledged nodes, and we ignore the sentinels.

Taking the book's hint, we start by showing that with at most $n - 1$ right rotations, we can convert any binary search tree into one that is just a right-going chain. The idea is simple. Let us define the right spine as the root and all descendants of the root that are reachable by following only right pointers from the root. A binary search tree that is just a right-going chain has all n nodes in the right spine.

As long as the tree is not just a right spine, repeatedly find some node $y$ on the right spine that has a non-leaf left child $x$ and then perform a right rotation on $y$:

(In the above figure, note that any of $\alpha$, $\beta$, and $\gamma$ can be an empty subtree.) Observe that this right rotation adds $x$ to the right spine, and no other nodes leave the right spine. Thus, this right rotation increases the number of nodes in the right spine by $1$. Any binary search tree starts out with at least one node—the root—in the right spine. Moreover, if there are any nodes not on the right spine, then at least one such node has a parent on the right spine. Thus, at most $n - 1$ right rotations are needed to put all nodes in the right spine, so that the tree consists of a single right-going chain.

If we knew the sequence of right rotations that transforms an arbitrary binary search tree $T$ to a single right-going chain $T'$, then we could perform this sequence in reverse—turning each right rotation into its inverse left rotation—to transform $T'$ back into $T$.

Therefore, here is how we can transform any binary search tree $T_1$ into any other binary search tree $T_2$. Let $T'$ be the unique right-going chain consisting of the nodes of $T_1$ (which is the same as the nodes of $T_2$). Let $r = \langle r_1, r_2, \ldots, r_k \rangle$ be a sequence of right rotations that transforms $T_1$ to $T'$, and let $r' = \langle r_1', r_2', \ldots, r_{k'}' \rangle$ be a sequence of right rotations that transforms $T_2$ to $T'$. We know that there exist sequences $r$ and $r'$ with $k$, $k' \le n - 1$. For each right rotation $r_i'$, let $l_i'$ be the corresponding inverse left rotation. Then the sequence $\langle r_1, r_2, \ldots, r_k, l_{k'}', l_{k' - 1}', \ldots, l_2', l_1' \rangle$ transforms $T_1$ to $T_2$ in at most $2n - 2$ rotations.

13.2-5 $\star$

We say that a binary search tree $T_1$ can be right-converted to binary search tree $T_2$ if it is possible to obtain $T_2$ from $T_1$ via a series of calls to $\text{RIGHT-ROTATE}$. Give an example of two trees $T_1$ and $T_2$ such that $T_1$ cannot be right-converted to $T_2$. Then, show that if a tree $T_1$ can be right-converted to $T_2$, it can be right-converted using $O(n^2)$ calls to $\text{RIGHT-ROTATE}$.

We can use $O(n)$ calls to rotate the node which is the root in $T_2$ to $T_1$'s root, then use the same operation in the two subtrees. There are $n$ nodes, therefore the upper bound is $O(n^2)$.