
\documentclass[12pt]{article}
\usepackage{fullpage}


\begin{document}
\begin{center}
\bf 
CS 141, Advanced Topics in Algorithms \\
Spring 2004\\
Homework 3a  \\
Due Wednesday,  February 4
\end{center}
\vspace{0.5cm}

\begin{enumerate}

\item \textbf{[25 Points] Analyzing Insertion into Splay Trees.}
In class we analyzed the amortized cost of performing a FIND in a splay
tree.  We showed that while the actual cost of the FIND is $d$ (where $d$
is the depth of the last node visited during the FIND), the change in
potential due to the subsequent splaying step was less than or equal to
$(3 \log_2 n) - d + 2$, giving us an amortized cost of $(3 \log_2 n) +2
\in O(\log_2 n)$.\footnote{That ``+2'' term did not show up in the analysis that we did in class.
It comes from the analysis of the ``zig'' rule which we omitted in our discussion.}

Now let's find the amortized cost of performing an INSERT in a splay
tree.  The actual cost of the insertion and subsequent splaying is $d$,
the depth of the leaf at which the insertion is performed.  However, the
amortized cost will be less because of the potential change.  The
potential changes in two ways.  First the potential changes because a
node is inserted at the bottom of the tree, increasing the rank, $r(v)$,
of each node on the path from the root to this leaf.  Next, the potential
changes due to the splay.   We already know that the splay operation
contributes a change of potential which is less than or equal to $(3
\log_2 n) - d + 2$.  So, we only need to determine the change in
potential due to the increase in ranks along the insertion path.

Let $n(v)$ and $r(v)$ denote the number of nodes in the tree rooted at
$v$ and the rank of $v$, respectively, before the insertion.
Let $n'(v)$ and $r'(v)$ denote these values immediately after the
insertion (but before the splay).  Show that the change in the tree's
potential immediately after the insertion but before the splay is
$O(\log_2 n)$.  (Note:  To do this, write down the simple 
relationships that you can find between the various $n$, $r$, $n'$ and
$r'$ variables.  Then formulate a summation for the change in potential. 
Finally, find an upper-bound on this summation.) Now put everything
together to conclude that the amortized cost of an INSERT in a splay tree
is
$O(\log_2 n)$.

\end{enumerate}
\end{document}



