(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 und Kinder, wobei und 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 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 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 Kinder.
Alle Pfade von der Wurzel zu einem Blatt haben gleiche Tiefe

Kennzeichnung der inneren Knoten

Jeder innere Knoten besteht aus folgenden Bezeichnern:

Sei $\rho _{v}$ die Anzahl der Kinder von .
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

Basierend auf einem Artikel in:

Wikipedia.de