%% This LaTeX-file was created by <jl> Tue Feb  3 00:23:53 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}

day 7 2/2/98 ``1, 2, 3, 4, 5, 6, 7, 8, 9. There should be 9 of these, right?''


\section{Treaps}

\begin{itemize}
\item keys \( \{1,...,n\} \)
\item priority \( p(k)\in [0,1] \). if \( k\neq l \) then \( p(k)\neq p(l) \)
\item T a tree with a key at each node.
\item T in heap order = \( \forall x,y\in T: \) \( x=parent(y) \) \( p(x)<p(y) \)
\end{itemize}

\subparagraph{Lemma: A heap order binary search tree always exists and is unique.}

proof: keys must satisfy in order constraint and heap ordering constraint. \( \exists  \)a
smallest (heap order) element. This must be the root. Every smaller (by key
order) element must be to the left of the root and larger (by key order) elements
must be to the right. Now induct ont he left and right subtrees.


\section{Random Treap}

A random treap has priorities of each of its elements assigned randomly.


\subsection{insert(k)}

\begin{enumerate}
\item insert k as a leaf
\item pick \( p(k) \) randomly
\item rotate k up till you are in heap order
\end{enumerate}

\subsection{delete(k)}

\begin{enumerate}
\item rotate k down to a leaf
\item remove k
\end{enumerate}

\subsection{Search(k)}

Search(k) is implemented in the same way as for other binary search trees.


\subsection{Search Timing analyses}

Let:

\begin{itemize}
\item \( C \) = total number of comparisons
\item \( C^{+} \) = total number of m>k comparisons
\item \( C^{-} \) = total number of m<k comparisons
\end{itemize}
Break the expected cost of a search is:

\( E_{C}(m)=E_{C^{+}}(m)+E_{C^{-}}(m) \)

Consider searching for \( m+.5 \). Then \( C^{+} \) will contain elements only from \( \{1,...,m\} \). and \( C^{-} \) will
contain elements only from \( \{m+1,...,n\} \). The probability that k in \( C^{+} \) is chosen will be
\( \frac{1}{m-k+1} \). \( \sum _{i=1}^{m}\frac{1}{m-i+1}=\Theta (ln(m)) \). Calculate the contribution from \( C^{-} \) in the same way, then add them together
to get \( E_{C}(m)=\Theta (ln(n)) \).


\subsection{Deletion timing analyses}

In order to delete, elements must be rotated to the leaves before removal. The
expected number of rotations is less than 2. This can be seen by noting that
rotations will follow the left most branch of the right child or the right most
branch of the left child, then calculating the odds of a long left most or right
most chain. Essentially, the tree is probabilistically ``fat'' in that almost
all nodes are near to a leaf.

\end{document}