\documentclass{article}
\input{6897-preamble}

\begin{document}
\psetnum{2}
\date{2005/02/14}
\begin{pset}
  \begin{lemma}
    Any binary search tree can be converted using $n$ rotations to the tree
    that consists solely of a linear chain of elements along the right
    spine.
  \end{lemma}
  \begin{proof}
    We repeatedly traverse the right spine of the tree until we find a
    node with a left child. We perform a rotation about this left
    child, moving it onto the right spine. The procedure terminates
    when no node on the left spine has a left child; at this point,
    the desired form has been reached. Note that no node is rotated
    once it is moved onto the spine; thus, no node is rotated twice,
    and at most $n$ rotations are used. 
  \end{proof}

  \begin{corollary}
    Any BST can be converted to any other BST over the same set of
    elements using $2n$ rotations.
  \end{corollary}
  \begin{proof}
    Suppose we wish to convert BST $A$ to BST $B$. The algorithm above
    gives a series of rotations that will convert $A$ to the
    right-spine chain $C$. Similarly, we can also obtain a series of
    rotations to transform $B$ into $C$. We can reverse the
    transformation by performing the rotations in reverse order, and
    rotating about the parent rather than the left child. This gives a
    procedure for converting $C$ into $B$. At most $2n$ rotations are
    required to transform $A$ to $C$ then to $B$.
  \end{proof}

  \begin{theorem}
    Given an online $\alpha$-competitive BST algorithm, we can
    construct an online BST algorithm with cost $\bigO{\min \set{\alpha
      \mathsf{OPT}, m \log n}}$ for $m$ operations.
  \end{theorem}
  \begin{proof}
    Our algorithm is as follows: we treat the access sequence as
    chunks of $n$ accesses. We initially use the $\alpha$-competitive
    algorithm to service requests, while maintaining a counter of the
    number of rotations performed during the chunk. If $n \log n$
    rotations are performed during a chunk, we transform the tree
    (using the algorithm above) to a balanced configuration, and use
    the trivial algorithm to handle further requests in the
    chunk. Before performing the transformation, we make a copy of the
    tree in memory. As we handle requests using the trivial algorithm,
    we use the in-memory copy to keep track of the state of the tree
    used by the $\alpha$-competitive algorithm (without actually
    performing the rotations on the real tree). At the end of the
    block of $n$ accesses, we transform the tree back to the state
    that the $\alpha$-competitive algorithm would have it in.

    For each chunk of $n$ accesses, this algorithm performs $\alpha
    \mathsf{OPT}$ rotations, provided that $\alpha \mathsf{OPT} \le n
    \log n$. Otherwise, the algorithm performs the initial $n \log n$
    rotations, $4n$ rotations to transform between the
    $\alpha$-competitive and trivial states, and $\bigO{n \log n}$
    rotations using the trivial algorithm, for a total of $\bigO{n
      \log n}$ rotations. Summing over the $\ceil{\frac{m}{n}}$
    chunks, the total cost for $m$ operations is $\bigO{\min
      \set{\alpha \mathsf{OPT}, m \log n}}$.
  \end{proof}
\end{pset}
\end{document}