\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{$(a,b)$-B\"aume}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Wir schreiben einen Knoten $v$ als 
$v = (w_1, k_1, w_2, k_2, \dots, w_{\ell}, k_{\ell-1}, w_\ell)$.
Dabei sind $w_1$, $w_2$, $\ldots$, $w_\ell$ die Kindknoten von $v$,
und $k_1$, $\ldots$, $k_{\ell-1}$ die in $v$ gespeicherten 
Schl\"ussel.

Es gilt $k_1 < k_2 < \dots < k_{\ell-1}$. Alle Schl\"ussel im
Teilbaum $w_i$ sind kleiner als $k_i$ und gr\"o\ss{}er als
$k_{i-1}$. 
Jeder innere Nichtwurzelknoten hat mindestens $a$ und
h\"ochstens $b$ Kinder. Die Wurzel hat mindestens $2$ und 
h\"ochstens $b$ Kinder. Dementsprechend enth\"alt jeder innere
Nichtwurzelknoten mindestens $a-1$ und h\"ochstens $b-1$ Schl\"ussel. 
Die Wurzel enth\"alt mindestens einen und h\"ochstens $b-1$
Schl\"ussel.

Einf\"ugen eines Schl\"ussels $k$ in einen $(a,b)$-Baum 
(der Einfachheit halber lassen wir den Wert weg).
\begin{verbatim}
put(k)
  v <- root  
  while v is not a leaf do
    write v as (w[1], k[1], w[2], k[2], ...., w[l-1], k[l-1], w[l])
    if k < k[1] then 
      v <- w[1]
    else if k > k[l-1] then
      v <- w[l]
    else if there is an i such that k[i-1] < k < k[i] then
      v <- w[i]
    else // there is an i with k = k[i] 
      return 
  // now v is a leaf
  if v contains k
    return
  insert k into v
  // now we need to split the nodes that overflow
  while v contains b keys do
    split v into v', k', v'' // see below
    if v is not the root then
      let p be the parent of v 
      insert v',k',v'' into p // see below
      v <- p
    else
      create a new root (v', k', v'')
      return
\end{verbatim}
Die Splitoperation und das Einf\"ugen in den Elternknoten sehen so
aus:
Sei $v = (w_1, k_1, \dots, w_{b-1}, k_b, w_{b+1})$ und
sei $m = (b + 1)/2$.
Dann ist $v'  = (w_1, k_1, \dots, w_m)$,
$v'' = (w_{m+1}, \dots, w_{b+1})$ und
$k'= k_m$.
Das Einf\"ugen in den Elternknoten geht so:
$p =  (\dots, k_{r-1}, v, k_r, \dots)
 \rightarrow (..., k_{r-1}, v', k', v'', k_r, \dots)$

L\"oschen eines Schl\"ussels $k$ aus einem $(a,b)$-Baum 

\begin{verbatim}
remove(k)
  find the node v that contains k (as above)
  if v is not a leaf then
    find the successor or predecessor k' of k // it does not matter which one
                                              // we take
    replace k by k' in v
    let k <- k' and v <- the leaf that contains k'
  // now v is a leaf
  remove k from v
  // now we need to fix the underflow 
  while v contains a-2 keys and v is not the root do
    if v has a sibling with >=a keys then
      borrow a key from the sibling // see below
      return
    else
      // both siblings contain a-1 keys
      merge v with a sibling // either left or right sibling is fine. See below
      v <- parent of v 
  if v is the root and v contains no keys then
    remove v and let the new root be the child of v
\end{verbatim}

Das Borgen von dem rechten Geschwisterknoten $v'$ sieht so aus:
Im Elternknoten stehe $(\dots, v, k'', v', \dots)$,
wobei $v = (w_1, k_1,  \dots, k_{a-2}, w_{a-1})$ 
und $v' = (w'_1, k'_1, \dots)$ mindestens $a$ Schl\"ussel enth\"alt.
Dann
$v \leftarrow (w_1, k_1, \dots, k_{a-2}, w_{a-1}, k'', w'_1)$
und $v' \leftarrow  (w'_2, k'_2, \dots)$
und im Elternknoten \"andert sich der Eintrag zu
$(\dots,  v, k'_1, v', \dots)$.
In Worten: Der Schl\"ussel zwischen $v$ und $v'$ im Elternkoten wandert nach $v$,
das linkeste Kind von $v'$ wird das rechteste Kind von $v$ und der linkeste
Schl\"ussel von $v'$ wandert in den Elternknoten zwischen $v$ und $v'$.
Das Borgen vom linken Geschwisterknoten geht analog.

Das Verschmelzen mit dem rechten Geschwisterknoten geht so:
Im Elternknoten stehe $(\dots, v, k, v', \dots)$,
wobei $v = (w_1, k_1,  \dots, k_{a-2}, w_{a-1})$
und $v' = (w'_1, k'_1, \dots, k'_{a-1}, w'_{a})$.
Wir verschmelzen $v$ und $v'$ zu
$v'' = (w_1, k_1, \dots, k_{a-2}, w_{a-1}, k, w'_{1}, k'_{1}, \dots, k'_{a-1}, w'_{a})$.
Der Elternknoten \"andert sich folgenderma\ss{}en
$(\dots, v, k, v', \dots) \rightarrow (\dots, v'', \dots)$.
In Worten:
$v$ und $v'$ werden aneinander geh\"angt, und der Schl\"ussel, der $v$ und $v'$ im
Elternknoten trennt, wird nach unten gezogen.
Das Verschmelzen mit dem linken Geschwisterknoten geht analog.

Beachte: Wenn der Elternknoten den Grad 2 hat,
kann es durch Verschmelzen passieren, dass er hinterher
keine Schl\"ussel mehr enth\"alt. Handelt es sich
beim Elternknoten um die Wurzel, so kann man sie danach
l\"oschen. Handelt es sich um einen inneren Knoten
(wenn $a=2$), verf\"ahrt man gem\"a\ss{} des obigen Algorithmus und
f\"ullt den Knoten vom Grad $1$ durch Borgen oder Verschmelzen wieder
auf.
\end{document}