\documentclass[12pt]{article}

\input{cps130.tex}

\begin{document}

\title{Splay Trees (10)}
\author{Michael L. Littman}
\date{October 8th, 1998}

\maketitle 

\section{SPLAY TREES}

\subsection{Review}

\ni We want to support fast insertions, deletions, and finds into a
binary search tree.

\ni Standard binary search trees don't cut it because operations take
too long: as much as $\Theta(n)$ for stringy trees.

\ni Balanced binary search trees remedy this, but are complex to
implement, and rebalancing has a fair amount of overhead.

\ni Splay trees are easy to implement, but tricky to analyze.  They
give bushy trees in an {\em amortized\/} sense, that we will discuss.


\subsection{Basic Idea}

\ni We allow the tree to become unbalanced.  

\ni The downside is that we might need to spend a lot of time finding
a node that is deeper than it ought to be.

\ni To make up for this, whenever we find a node, we move it up to the
top!

\ni Demonstrate rotation.

\subsection{Splaying a Node}

\ni Brings node $x$ to the top, two levels at a time.

\ni Three rotation-pair cases:

\ul

\li Zig: Child of root $w$... rotate node.

\li Zig-zag: Left child of a right child $z$ of $w$ or right child of
a left child... rotate node twice.

\li Zig-zig: Left child of a left child $y$ of $z$ or right child of a
right child... rotate parent, then rotate node.

\el

\subsection{Splay Example Step 1}

\ni \epsfig{file=figs10/t1.ps,width=2in}

\subsection{Splay Example Step 2}

\ni \epsfig{file=figs10/t2.ps,width=2.4in}

\subsection{Splay Example Step 3}

\ni \epsfig{file=figs10/t3.ps,width=2.25in}

\subsection{Splay Example Step 4}

\ni \epsfig{file=figs10/t4.ps,width=2.5in}

\subsection{Splay Example Step 5}

\ni \epsfig{file=figs10/t5.ps,width=2.3in}


\subsection{Splay Properties}

\ni We can observe what happens to the depth of various nodes in the
tree when we splay $x$.

\ul

\li The splayed node $x$?

% depth -> 0

\li Children of $x$?

% depth does not increase

\li Other nodes?

% depth increases at most once (then become children of x)
% actually a few nodes can go down by 2

\li Nodes along the path to the splayed node?

% increase by at most 2, then decrease at least one for every two
% steps x goes down.  thus, if depth was $i$, can go to $i+2$, then to
% something like $i/2$.

\el


\subsection{Operations Using Splays}

\ni We can perform all the standard binary-search-tree operations in
terms of splays.

\ul

\li Find: Locate the node, splay it to the top.  If node is not found,
splay last found node to the top.

\li Min: Find $-\infty$.

\li Max: Find $\infty$.

\li Successor: Find node.  Compute min of right subtree.  (Much
easier!)

\li Alternate insert: Find node.  Find min in right subtree (or max in
left subtree, depending on what was found).  It will have no left (or
right, respectively) child, and therefore a place for the new element.

\li Delete: Find node.  Find max of left subtree.  It will have no
right child, so make the right subtree the new right child.

\el

\subsection{Splay Sort}

\ni Do a sequence of inserts, then traverse the resulting tree.  How?

\ans{Find min, then a series of successors.}

\ni Running time: Clearly $O(n^2)$.  Why?

\ans{A splay just goes to the bottom and rotates back up.  That's
$O(n)$.  So, a sequence of $n$ is $O(n^2)$.}

\ni We will see, in fact, that any sequence of $k$ splays on a tree
with $n$ nodes runs in $O(k \log n)$.  Amazing!

\ni We will use potential functions and {\em amortized analysis\/} to
show this.

\ni Therefore, what is splay sort's running time?

\ans{$O(n \log n)$.}

\section{AMORTIZED ANALYSIS}

\subsection{Idea of Amortized Analysis}

\ni Closely related to the motivation for potential functions.

\ni Sometimes the worst-case running time of an operation does not
accurately capture the worst-case running time of a {\em sequence\/}
of operations.

\ni The idea of amortization is that we will charge induhvidual
operations with the {\em average\/} cost for all operations in the
sequence.

\ni So, if a sequence of 100 operations requires 1000 units of time,
we'll say each operation has an amortized cost of 10 (even if one of
them takes 901 units and the rest take unit time).

\subsection{Classic Example}

\ni Incrementing an $n$-bit binary number.

\ul
\li  0 1 1 0 0 1 1 1 1 0 0 1 1 1 + 1 =
\li  0 1 1 0 0 1 1 1 1 0 1 0 0 0
\li  (4 flips)
\el

\ni How many bit flips in the worst case?  Best case?

\ans{Can be all $n$, can be just $1$.}

\subsection{Increment Code}

\begin{verbatim}
bit *
increment(bit *x)
{
   int i = n-1;
   while (i >= 0  &&  bit[i] == 1) {
     bit[i] = 0;
     i--;
   }
   if (i >= 0)
     bit[i] = 1;

   return bit;
}
\end{verbatim}

\subsection{Counting Flips}

\ni Number of flips for incrementing all 7-bit numbers.  (Number is on
$x$ axis, number of flips on $y$.)  Can see the worst case, but it's
rare.

\ni \epsfig{file=figs10/ruler.ps,width=4.5in}


\subsection{Sequence of Flips}

\ni Total flips for incrementing, in sequence, all 5-bit numbers.

\ni \epsfig{file=figs10/accum.ps,width=4.5in}

\ni Note: Total number of flips for incrementing $0$ to $x$ never goes
above $2x+1$.

\ni When does it equal $2x+1$?

\ans{When $x$ is a power of 2.  You get that big kick at the end as a
bunch of ones turn to zeros.}

\subsection{Potential Function}

\ni We've been analyzing individual while loops with potential
functions.  This time, we'll analyze the entire ``increment''
operation.

\ni Let $x$ be the current value of the counter.  Let $\Phi(x)$ be a
potential function that returns the number of ``on'' bits in $x$.

\ni Let's say each bit flip costs one unit.

\ni The worst-case cost of increment number $t$ is $c_t \le n$.  We'll
define the amortized cost to be $\hat{c}_t = 2$.  That is, we'll {\em
pretend\/} that each increment costs $2$, even when it's really $n$
(or even if it's $1$).

\subsection{It Works!}

\ni We need to show that the fundamental inequality of potential
functions holds:
$$\hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t) \ge c_t.$$

\begin{eqnarray*}
\lefteqn{\hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t)}\\
&=& 2 + \Phi(x_{t-1}) - \Phi(x_t) \\
&=& 2 + \mbox{number of trailing ones in $x_{t-1}$ minus 1} \\
&=& 1 + \mbox{number of trailing ones in $x_{t-1}$} \\
&=& c_t
\end{eqnarray*}

\ni Note that the potential function measures the amount of work that
went into building the data structure.

\section{ANALYSIS OF SPLAY TREES}

\subsection{Splay Operations}

\ni Recall that inserts, deletes, and finds in a splay tree all
consist of some number of splay operations (moving a node to the root)
and a constant amount of pointer diddling.

\ni We will show that splay operations have $O(\log n)$ amortized time
and it will follow that a sequence of $n$ inserts and deletes on an
initially empty tree takes $O(\log n)$ per operation.

\ni Like a balanced tree, but not!


\subsection{Analysis Setup}

\ni Here's the setup for the analysis.  First, define the {\em size\/}
of a node $x$ to be the number of nodes in the subtree rooted at $x$.

\ul
\li A unit of work is a rotation.

\li A splay at some node $x$ up to the root $r$ is the operation, and
its amortized cost is $3(\log s(r)- \log s(x))+1$.

\li The potential function for a tree $T$ is $\Phi(T) = \sum_{x\in T}
\log(s(x))$.

\el

\ni We need to show that the operation of splaying a node $x$ to the
root satisfies the potential function inequality.  We'll do this one
case at a time.

\subsection{Case Setup}

\ni Let $s_{t-1}$ and $s_t$ be the size functions just before and
after the step.  Let $y$ be the parent of $x$ and $z$ be the parent of
$y$ (if it exists).

\ni We'll define the amortized cost to be $3(\log s_{t}(x)- \log
s_{t-1}(x))+1$ for Zig and $3(\log s_{t}(x)- \log s_{t-1}(x))$ for
the other cases.  The amortized cost for a sequence of $h$ steps
splaying $x$ up the tree, therefore, is
$$\sum_{t=1}^{h-1} 3(\log s_t(x)- \log s_{t-1}(x)) + 3(\log
s_h(x)- \log s_{h-1}(x))+1 = 3(\log s_h(x) - \log s_0(x)) + 1.$$

\ni This is $O(\log n)$.  Why?

\ans{$s_0(x) \ge 0$, $s_h(x) = n$.}

\ni This means that our amortized cost for each complete splay is
$O(\log n)$, even if we start deep in the tree.  The intuition is
that, the only way we could make the tree that deep in the first place
is to have performed operations that increase the potential
substantially.  So, the average still works out.

\subsection{Zig Case}

\ni We need to show that $\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t) \ge
c_t$.

\ni Here, we'll take $\hat{c}_t =  3(\log s_{t}(x)- \log
s_{t-1}(x))+1$.  The actual cost $c_t = 1$.  Why?

\ans{Zig is one rotation.}

\begin{eqnarray*}
\lefteqn{\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t)}\\
&=& 3(\log s_{t}(x)- \log s_{t-1}(x)) + 1 + \sum_{w\in T} \log(s_{t-1}(w)) -
	\sum_{w\in T} \log(s_{t}(w)) \\
&=& 3\log s_{t}(x)- 3 \log s_{t-1}(x) + 1 
	+ \log(s_{t-1}(x)) + \log(s_{t-1}(y))
	- \log(s_{t}(x)) - \log(s_{t}(y))\\
&=& 2\log s_{t}(x)- 2 \log s_{t-1}(x) + 1 + \log(s_{t-1}(y)) - \log(s_{t}(y))\\
&\ge& 2(\log s_{t}(x)-  \log s_{t-1}(x)) + 1\\
&\ge& 1 = c_t.
\end{eqnarray*}

\ans{First step: Only $x$ and $y$ change sizes.  Next step: $s_t(y)\le
s_{t-1}(y)$.  Finally, $s_t(x)\ge s_{t-1}(x)$.}


\subsection{Zig-Zig Case}

\ni We're splaying $x$, with $y$ and $z$ as the immediate parents.

\ni We need to show that $\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t) \ge
c_t$.

\ni Here, we'll take $\hat{c}_t =  3(\log s_{t}(x)- \log
s_{t-1}(x))$.  The actual cost $c_t = 2$.  Why?

\ans{Zig-zig is two rotations.}

\begin{eqnarray*}
\lefteqn{\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t)}\\
&=& 3(\log s_{t}(x)- \log s_{t-1}(x)) + \sum_{w\in T} \log(s_{t-1}(w)) -
	\sum_{w\in T} \log(s_{t}(w)) \\
&=& 3\log s_{t}(x)- 3 \log s_{t-1}(x)  
	+ \log(s_{t-1}(x)) + \log(s_{t-1}(y))+ \log(s_{t-1}(z))
	- \log(s_{t}(x)) - \log(s_{t}(y))- \log(s_{t}(z))\\
&\ge& 2\log s_{t}(x)- \log s_{t-1}(x) - \log(s_{t}(z))\\
&\ge& 2.
\end{eqnarray*}

\ans{First step: Only $x$, $y$, and $z$ change sizes.  Next step:
$s_t(x)= s_{t-1}(z)$ and $s_t(x) \ge s_t(y)$ and $s_{t-1}(y) \ge
s_{t-1}(x)$.} 

\ni The last step here is sort of tricky.

\ul

\li Claim: $2 \log s_t(x) - \log s_{t-1}(x) - \log s_t(z) \ge 2$.

\li Let $n = s_t(x)$.

\li Note that if $a+b = n$, then $-\log a - \log b \ge -2\log n + 2$,
and this is attained at $n/2$ (this isn't hard to show with calculus).

\li Note that $s_t(z) + s_{t-1}(x) = n$.  So, 

\begin{eqnarray*}
\lefteqn{2 \log s_t(x) - \log s_{t-1}(x) - \log s_t(z)} \\
&\ge& 2 \log n - 2\log n + 2\\
&=&  2.
\end{eqnarray*}

\el

\ni Zig-zag case a little different, but same result.


\subsection{Entire Splay}

\ni Repeating this analysis for each pair of rotations as we go up,
plus the final single rotation if needed, we get a total amortized
cost of $3(\log n - \log s_0(x)) + 1 = O(\log n)$, where the potential
function inequality is satisfied (string them all together).

\ni Therefore, a splay operation in a tree of size $n$ has an
amortized cost of $O(\log n)$.  So, a sequence of $k$ splays will cost
$O(k \log n)$.

\end{document}
