(a, b)-Baum

Abbildung 1: (2, 4)-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.

Siehe auch

• B-Baum
• Suchbaum

Weblinks

• https://tcs.rwth-aachen.de/lehre/DA/SS2011/handout-2011-05-03.pdf
• https://daphne.informatik.uni-freiburg.de/svn-public/AlgoDatSS2015/public/folien/vorlesung-08b.pdf