mini|rechts|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.Paul E. Black: In: Vreda Pieterse, Paul E. Black (Hrsg.): Dictionary of Algorithms and Data Structures. 6. Oktober 2004, abgerufen am 20. Juni 2015.
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 B-Baum Suchbaum
Weblinks https://tcs.rwth-aachen.de/lehre/DA/SS2011/handout-2011-05-03.pdf https://daphne.informatik.uni-freiburg.de/svn-public/AlgoDatSS2015/public/folien/vorlesung-08b.pdf
Einzelnachweise
Kategorie:Suchbaum Kategorie:Datenbankindex