%% This LaTeX-file was created by <jl> Wed Jan 28 11:49:33 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day6 1/28/98 quote of the day ``This is a big mess, right?''


\section{Splay Trees}

Always move an element you are interested in to the root. Capitol letters are
trees and lowercase letters are elements in the following

Split(i,S) will do Insert(i,S) then Splay(i,S) where Splay(i,S) moves i to the
root of the tree by rotations.


\subsection{Splay(x,S)}

\begin{enumerate}
\item while (x not root)
\item parent(x)=y, parant(y)=z if z exists
\item \( !\exists z \) then rotate(x)
\item \( \exists z \) 
\end{enumerate}
\begin{itemize}
\item case a: z>y>x or x>y>z then rotate(y); rotate(x) 
\item case b: z>x>y or y>x>z then rotate(x); rotate(y)
\end{itemize}

\subsection{Timing analysis}

Definitions

\begin{itemize}
\item \( |S|= \) \# nodes in tree S
\item \( S(x)= \) subtree rooted at x
\item \( \mu (s)=\left\lfloor log|S|\right\rfloor  \)
\item \( \mu (x)=\mu (S(x)) \)
\item \( \overline{\mu }(S)=\Sigma _{x\in S}\mu (x) \)
\end{itemize}
3 credit cards to charge costs to:

visa, mastercard (MC), americanexpress (AE)

\begin{itemize}
\item \( !\exists z \) -> AE
\item \( \exists z \) , case 1. if \( \overline{\mu }(S')<\overline{\mu }(S) \) then visa else MC
\end{itemize}
\( \overline{\mu } \) is a measure of how balanced a tree is. For a completely unbalanced tree,
\( \overline{\mu }(S)=O(n*log(n)) \). For a totally balanced tree, \( \overline{\mu }(S)=O(n) \)

after m splay(x,S) calls

\begin{itemize}
\item \( AE\leq m \)
\item \( MC \)
\end{itemize}

\subparagraph{lemma: \protect\( \overline{\mu }(S')\geq \overline{\mu }(s)\Rightarrow \mu (x')>\mu (x)\protect \)}

in all cases \( \overline{\mu }(x')\geq \mu (x) \) because x is moving up in the tree.

The lemma, together with \( \mu (x)\leq log(n) \) means \( MC\leq m*log(n) \) because \( \mu (x) \) can increase at least \( 1 \) to \( log(n) \).

\begin{itemize}
\item \( Visa\leq \overline{\mu }(S_{begin})-\overline{\mu }(S_{end})+ \) something more due to the times when the MC is charged
\end{itemize}

\subparagraph{lemma: \protect\( \overline{\mu }(S')-\overline{\mu }(S)\leq 2(\mu (x')-\mu (x))\protect \) }

The total ``something more'' is less than \( 2*log(n) \) for each splay. 

\( Visa\leq \overline{\mu }(S_{begin})-\overline{\mu }(S_{end})+2m*log(n) \) 


\paragraph{Theorem: m splays in a tree of size n will do at most \protect\( 3m*log(n)+n*log(n)+m\protect \) rotations.}

proof: add up AE, MC, and Visa

\end{document}