13.2 Rotations

13.2-1

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

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.)

Consider transforming an arbitrary $n$-node binary tree into a right-going chain as follows:

Let the root and all successive right children of the root be the elements of the chain initial chain. For any node $x$ which is a left child of a node on the chain, a single right rotation on the parent of $x$ will add that node to the chain and not remove any elements from the chain. Thus, we can convert any binary search tree to a right chain with at most $n − 1$ right rotations.

Let $r_1, r_2, \dots, r_k$ be the sequence of rotations required to convert some binary search tree $T_1$ into a right-going chain, and let $s_1, s_2, \dots, s_m$ be the sequence of rotations required to convert some other binary search tree $T_2$ to a right-going chain. Then $k < n$ and $m < n$, and we can convert $T_1$ to $T_2$ by performing the sequence $r_1, r_2, \dots, r_k, s_m', s_{m - 1}', \dots, s_1'$ where $s_i'$ is the opposite rotation of $s_i$. Since $k + m < 2n$, the number of rotations required is $O(n)$.

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)$.