(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 ${\displaystyle (a,b)}$-Baum haben alle Teilbäume die gleiche Tiefe, und alle inneren Knoten – außer der Wurzel – haben zwischen ${\displaystyle a}$ und ${\displaystyle b}$ Kinder, wobei ${\displaystyle a}$ und ${\displaystyle b}$ natürliche Zahlen sind, die die Eigenschaft ${\displaystyle 2\leq a\leq (b+1)/2}$ erfüllen müssen. Die Wurzel hat, falls sie kein Blatt ist, zwischen 2 und ${\displaystyle b}$ Kinder.^[1]

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

Definition

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

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

Kennzeichnung der inneren Knoten

Jeder innere Knoten ${\displaystyle v}$ besteht aus folgenden Bezeichnern:

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

Einzelnachweise

1. Paul E. Black: (a,b)-tree. (Memento vom 13. Oktober 2018 im Internet Archive) In: Vreda Pieterse, Paul E. Black (Hrsg.): Dictionary of Algorithms and Data Structures. 6. Oktober 2004, abgerufen am 20. Juni 2015.