(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.^[1]

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

Definition Bearbeiten

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 Bearbeiten

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 Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

↑ 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.

[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.

[1]