\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Skiplisten}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Darstellung}

Eine Skipliste besteht aus
mehreren Listen.
Ein Knoten \texttt{n} in einer Liste hat folgende 
Felder:
\begin{itemize}
  \item \texttt{k}, \texttt{v}: Schl\"ussel und Wert
  \item \texttt{pred}, \texttt{succ}: Vorg\"anger- und
    Nachfolgerknoten von \texttt{n} (horizontal)
  \item \texttt{down}: entsprechender Knoten unter \texttt{n}
    (vertikal)
\end{itemize}

Jede Liste hat zwei \emph{Pseudoknoten}, am Anfang und am Ende,
mit Schl\"ussel $-\infty$ und $+\infty$.
Zu Beginn besteht die Skipliste 
nur aus der untersten Liste, welche
aus den Pseudoknoten besteht.


\section{Vorg\"angerliste}

Die Funktion \texttt{search} liefert einen 
Stack \texttt{Q}, der die Vorg\"angerknoten 
f\"ur Schl\"ussel \texttt{k} 
(bzw.~die Knoten mit Schl\"ussel \texttt{k}) in allen 
Listen der Skipliste enth\"alt (von unten nach oben).

\begin{verbatim}
search(k)
  Q <- new Stack
  n <- -INFTY pseudonode of highest list 
  do
    while n.next.k <= k do
      n <- n.next 
    Q.push(n)
    n <- n.down
  while n != NULL
  return Q 
\end{verbatim}

\section{Einf\"ugen}

\begin{verbatim}
put(k, v)
  Q <- search(k)
  n <- Q.pop
  if n.k == k then
    n.v <- v
    return
  insert a new node for (k, v) after n
  while coinFlip == head do
    if Q.isEmpty then
      create a new list with -INFTY, a node for k, +INFTY
      create vertical links 
    else
      n <- Q.pop
      insert a new node for k after n, add a vertical link
\end{verbatim}

\section{L\"oschen}

\begin{verbatim}
remove(k)
  Q <- search(k)
  n <- Q.pop
  if n.k != k then
    throw NoSuchElementException
  while n != NULL and n.k == k do
    remove n from the list
    if !Q.isEmpty do
      n <- Q.pop
    else
      n <-NULL
  remove pseudonodes for empty lists, if necessary
\end{verbatim}

Die Funktionen
\texttt{get(k)}, \texttt{pred(k)}, \texttt{succ(k)},
\texttt{min} und \texttt{max} sind eine \"Ubung.

\end{document}