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 2^k Knoten und die Höhe k besitzt.

Anwendung

Binomialbäume werden beispielsweise in Binomial-Heaps, einer speziellen Implementation von Heaps verwendet.