(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:

Kennzeichnung der inneren Knoten

Jeder innere Knoten v besteht aus folgenden Bezeichnern:

Siehe auch

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 27.02. 2020