\begin{frame}[fragile]
\frametitle{Skip lists - Searching}
\begin{itemize}
\item Walk right in top linked list until going right would go too far
\item Walk down to bottom linked list
\item Walk right in bottom list until element found (or not)
\end{itemize}
\begin{figure}[b!]
\centerline{\includegraphics[scale=0.5]{twolists}}
\end{figure}
\end{frame}
\begin{frame}[fragile]
\frametitle{Skip lists - Searching}
QUESTION: Which nodes should be in each level?
\begin{itemize}
\item The bottom level must contain all elements
\item We could try to put ``popular'' elements at higher levels
\item Typically we won't have this information and here we care about worst-case performance
\item Best approach: Evenly space the nodes in the top level
\item But how many nodes should we choose?
\end{itemize}
\begin{figure}[b!]
\centerline{\includegraphics[scale=0.5]{twolists}}
\end{figure}
\end{frame}