(a,b)-Baeume

Wir schreiben einen Knoten v als 
v = (w[1], k[1], w[2], k[2], ...., w[l-1], k[l-1], w[l]).
Dabei sind w[1], w[2], ..., w[l] die Kindknoten von v,
und k[1], ..., k[l-1] die in v gespeicherten Schluessel.

Es gilt k[1] < k[2] < ... < k[l-1]. Alle Schluessel im
Teilbaum w[i] sind kleiner als k[i] und groesser als
k[i-1]. 

Jeder innere Nichtwurzelknoten hat mindestens a und
hoechstens b Kinder. Die Wurzel hat mindestens 2 und 
hoechstens b Kinder. Dementsprechend enthaelt jeder innere
Nichtwurzelknoten mindestens a-1 und hoechstens b-1 Schluessel. 
Die Wurzel enthaelt mindestens einen und hoechstens b-1 
Schluessel.

Einfuegen eines Schluessels k in einen (a,b)-Baum 
(der Einfachheit halber lassen wir die Zuweisung des Wertes
 weg).

put(k)
  v <- root  
  while (v is not a leaf)
    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)
    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

Die Splitoperation und das Einfuegen in den Elternknoten sehen so
aus:
Sei v = (w[1], k[1], w[2], k[2], ...., w[b-1], k[b], w[b+1]) und
sei m = (b + 1)/2. 
Dann ist v'  := (w[1], k[1], ..., w[m])
         v'' := (w[m+1], ..., w[b+1])
         k'   := k[m]

Das Einfuegen in den Elternknoten geht so:
   p =  (..., k[r-1], v, k[r], ...)
 -> (..., k[r-1], v', k', v'', k[r], ...)

Loeschen eines Schluessels k aus einem (a,b)-Baum 

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)
    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


Das Borgen von dem rechten Geschwisterknoten v' sieht so aus:
Im Elternknoten stehe 
       (..., v, k'', v'...),
wobei v = (w[1], k[1],  ..., k[a-2], w[a-1]) 
und v' = (w'[1], k'[1], ...) mindestens a Schluessel enthaelt.
Dann
  v <- (w[1], k[1],  ..., k[a-2], w[a-1], k'', w'[1])
  v' <-  (w'[2], k'[2], ...)
und im Elternknoten aendert sich der Eintrag zu
       (..., v, k'[1], v'...),

In Worten:
Der Schluessel zwischen v und v' im Elternkoten wandert nach v,
das linkeste Kind von v' wird das rechteste Kind von v, und der linkeste
Schluessel von v' wandert in den Elternknoten zwischen v und v'.

Das Borgen von dem linken Geschwisterknoten geht analog.

Das Verschmelzen mit dem rechten Geschwisterknoten geht so:
Im Elternknoten stehe (..., v, k, v', ...),
wobei v = (w[1], k[1],  ..., k[a-2], w[a-1]) 
und v' = (w'[1], k'[1], ..., k'[a-1], w'[a]).
Wir verschmelzen v und v' zu
v'' = (w[1], k[1], ..., k[a-2], w[a-1], k, w'[1], k'[1], ..., k'[a-1], w'[a]).
Der Elternknoten aendert sich folgendermassen
(..., v, k, v', ...) -> (..., v'', ...).

In Worten:
v und v' werden aneinandergehaengt, und der Schluessel, 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 Schluessel mehr enthaelt. Handelt es sich
  beim Elternknoten um die Wurzel, so kann man sie danach
  loeschen. Handelt es sich um einen inneren Knoten
  (wenn a=2), verfaehrt man gemaess des obigen Algorithmus und
  fuellt den Knoten vom Grad 1 durch Borgen oder Verschmelzen wieder
  auf.