(a, b)-Baum

Spezialfall einer Baum Datenstruktur
(Weitergeleitet von (a,b)-Baum)

Der (a, b)-Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out-Trees.

Abbildung 1: (2, 4)-Baum

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.

Definition

Bearbeiten

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

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

Bearbeiten
Bearbeiten

Einzelnachweise

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.