(a, b)-Baum
Der (a, b)-Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out-Trees.
Bei einem -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 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 natürliche Zahlen mit . Dann ist der Out-Tree ein -Baum, falls gilt:
- Für innere Knoten außer der Wurzel ist Ausgangsgrad .
- 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 die Anzahl der Kinder von .
- Seien die Kanten zu den Kindern.
- Sei eine sortierte Liste von Schlüsseln, wobei gleich dem größten Schlüssel im Teilbaum mit Wurzel ist.
Siehe auch
Basierend auf einem Artikel in:
Wikipedia.de
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 27.02. 2020