Binomialbaum der Ordnung 3
Ein Binomialbaum ist in der Graphentheorie ein
spezieller Baum (Graphentheorie), dessen Struktur
durch seine Ordnung eindeutig festgelegt ist.
Definition
Binomialbäume und ihre Ordnung sind wie folgt rekursiv definiert:
- Ein Binomialbaum der Ordnung 0 besteht aus einem einzelnen Knoten.
- Ein Binomialbaum der Ordnung k besitzt eine Wurzel mit Grad
k deren Kinder genau die Ordnung k-1, k-2, ..., 0 (in dieser
Reihenfolge) besitzen.
Eigenschaften
Ein Binomialbaum der Ordnung k lässt sich auch leicht aus zwei Binomialbäumen der Ordnung k-1 erstellen,
indem einer der beiden Bäume zum am weitesten links stehenden Kind des anderen gemacht wird. Aus dieser Konstruktion lässt sich
leicht per vollständiger Induktion die Eigenschaft
ableiten, dass ein Binomialbaum der Ordnung k genau 2k Knoten und die Höhe k besitzt.
Anwendung
Binomialbäume werden beispielsweise in Binomial-Heaps, einer
speziellen Implementation von Heaps verwendet.
|
