-baum.svg)
(a, b)-Baum
Spezialfall einer Baum Datenstruktur
From Wikipedia, the free encyclopedia
Der (a, b)-Baum ist eine Datenstruktur in der Informatik und Spezialfall eines Baumes speziell eines Out-Trees.
-baum.svg)
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
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.
![{\displaystyle S_{v}[1\dots \rho _{v}]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/940e5aaddc38a94cb4dfbc7717d73831ecc0292b)
![{\displaystyle H_{v}[1\dots \rho _{v}-1]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/991ab321ee4d679a64de75c26e9bfa0d0008dea8)
![{\displaystyle H_{v}[i]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/19724308bb4f9c608be8ab9c29460bb789d4433b)
![{\displaystyle S_{v}[i]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/a51cbe22f47a52c0f164ddf8505f583be9ea4f1c)