13.2 Rotations

13.2-1

Write pseudocode for \(\text{RIGHT-ROTATE}\).

C++
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)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用