\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}