(a, b)-Baum

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
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 -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.[1]

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

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

[Bearbeiten | Quelltext bearbeiten]

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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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.