(a, b)-Baum
# (a, b)-Baum

Der (a, b)-Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out-Trees.

Bei einem $(a,b)$-Baum haben alle Teilbäume die gleiche Tiefe, und alle inneren Knoten – außer der Wurzel – haben zwischen $a$ und $b$ Kinder, wobei $a$ und $b$ natürliche Zahlen sind, die die Eigenschaft $2\leq a\leq (b+1)/2$ erfüllen müssen. Die Wurzel hat, falls sie kein Blatt ist, zwischen 2 und $b$ Kinder.

Die Schlüssel und Datenelemente werden nur in den Blättern gespeichert.

## Definition

Seien $a,b\in \mathbb {N}$ natürliche Zahlen mit $2\leq a\leq (b+1)/2$. Dann ist der Out-Tree $T$ ein $(a,b)$-Baum, falls gilt:

* Für innere Knoten außer der Wurzel ist $a\leq$ Ausgangsgrad $\leq b$.
* Die Wurzel hat höchstens $b$ Kinder.
* Alle Pfade von der Wurzel zu einem Blatt haben gleiche Tiefe

## Kennzeichnung der inneren Knoten

Jeder innere Knoten $v$ besteht aus folgenden Bezeichnern:

* Sei $\rho _{v}$ die Anzahl der Kinder von $v$.
* Seien $S_{v}[1\dots \rho _{v}]$ die Kanten zu den Kindern.
* Sei $H_{v}[1\dots \rho _{v}-1]$ eine sortierte Liste von Schlüsseln, wobei $H_{v}[i]$ gleich dem größten Schlüssel im Teilbaum mit Wurzel $S_{v}[i]$ ist.
