Hilfe Hauptseite Vorherige Naechste
Logo
Navigationsleiste
1. Der Binomial Heap Algorithmus / 3. Der Binomial Heap

3.1 Der Binomialbaum


Einleitung Wie beschrieben, ist ein Binomial Heap ein Wald von Binomialbäumen. Um den Binomial Heap verstehen zu können, muß deshalb erst der Binomialbaum definiert werden.

Definition des Binomialbaums Der Binomialbaum Bk ist ein geordneter Baum, welcher rekursiv wie folgt definiert ist:
  1. B0 ist ein aus genau einem Knoten bestehender Baum.
  2. Bn+1 entsteht aus zwei Bn Bäumen, indem diese miteinander verbunden werden:
    Die Wurzel eines Bn wird als Sohn an die Wurzel des anderen Bn gehängt.
Folgende Grafik zeigt die Binomialbäume Bk für k = 0, ..., 3:



Eigenschaften des Binomialbaums Wie aus der Grafik ersichtlich, haben Binomialbäume folgende Eigenschaften:
  1. Ein Binomialbaum Bn besteht aus genau 2n Knoten.
  2. Ein Binomialbaum Bn hat die Höhe n.
  3. Die Wurzel des Binomialbaums Bn hat n Söhne.
  4. Die n Teilbäume der Wurzel von Bn sind Bn-1, Bn-2, ... , B0
  5. Bn hat (n über i) Knoten mit Tiefe i

Die Heapordnung Da ein Binomialbaum zur Speicherung von Elementen, für die eine Ordnung definiert ist, verwendet werden soll, besitzt der Baum weiterhin folgende Eigenschaft:
Für jeden Knoten gilt, daß der in ihm gespeicherte Schlüssel kleiner ist als die Schlüssel seiner Söhne. Bäume mit dieser Eigenschaft werden "heapgeordnet" genannt, und es ist bei ihnen durch diese Eigenschaft immer gewährleistet, daß sich das kleinste in ihnen gespeicherte Element an der Wurzel des Baumes befindet. Dadurch wird ein schneller Zugriff auf das Element mit dem kleinsten Schlüssel in diesem Baum ermöglicht.

Baue einen B3-Baum: Nach dieser recht trockenen Definition soll jetzt eine kleine Aufgabe folgen:
In dem folgenden Applet findest du 8 B0-Bäume. Setze diese zu einem B3-Baum mit 8 Knoten zusammen. Du kannst zwei Knoten miteinander verbinden, indem du zuerst den Sohn auswählst, und dann mittels eines Mausklicks dem Applet mitteilst, an welchen Knoten dieser Sohn gehängt werden soll.
Mit dem Auswahlmenü kannst du zwischen den verschiedenen Beispielen wählen und die aktuelle Aufgabe in den Ausgangszustand zurücksetzen.

Das Bauen - Applet

Wie oben beschrieben, kann ein Binomialbaum nur zur Speicherung von 2n Elementen verwendet werden. Da in einem Priority Queue aber beliebig viele Elemente gespeichert werden sollen, ist ein einzelner Binomialbaum nicht dazu geeignet, einen Priority Queue zu speichern. Dazu wird der Binomial Heap benutzt.


1. Der Binomial Heap Algorithmus / 3. Der Binomial Heap
Seitenanfang Vorherige Naechste
Navigationsleiste