Linksbaum

Ein Linksbaum oder Linksheap ist ein Binärbaum, der als Vorrangwarteschlange benutzt werden kann. Diese Datenstruktur ist eine Erfindung von Clark Allan Crane und nutzt eine Heapstruktur. Linksbäume fordern im Gegensatz zu balancierten Binärbäumen nicht, dass jeder Pfad höchstens logarithmische Länge hat. Es genügt, dass es von jedem Knoten einen logarithmisch langen Pfad zu einem Blatt gibt und dieser bekannt ist. Linksbäume können effizient verschmolzen werden.

Definition

Ein Linksbaum ist definiert über eine Menge von total geordneten Schlüsseln. Die auf den Schlüsseln definierte Ordnung bestimmt die Priorität eines Schlüssels.

• Ein Knoten mit Distanz 0 und einem Schlüssel minimaler Priorität ist ein Linksbaum.
• Ein Knoten mit zwei Linksbäumen als Kinder ist ein Linksbaum, falls:
  • Sein Schlüssel mindestens so hohe Priorität hat wie die Schlüssel seiner Kinder (Heap-Eigenschaft).
  • Das linke Kind mindestens so große Distanz hat wie das rechte Kind.
  • Seine Distanz um genau 1 größer ist als die Distanz des rechten Kindes.

Die Definition impliziert, dass die Distanz die Länge des kürzesten Pfades zu einem Blatt misst. Folgt man in einem Linksbaum immer dem rechten Kind, so geht man einen solchen kürzesten Pfad.

Operationen

Ein Linksbaum mit n Schlüsseln unterstützt die folgenden Operationen garantiert in O(log n ) Zeit:

• insert – zum Einfügen eines Elementes,
• extractMin – zur Rückgabe und zum Entfernen eines Elementes mit höchster Priorität und
• merge – zum Verschmelzen zweier Heaps.

Algorithmen

Merke, dass hier ein Knoten mit Distanz 0 einen leeren Linksbaum darstellt. In einer Implementierung wird ein solcher für gewöhnlich als null-Zeiger dargestellt.

Verschmelzen (merge)

Diese Operation soll zwei Linksbäume zu einem neuen Linksbaum verschmelzen.

Sei K der Baum mit kleinerer Priorität und G der Baum mit größerer Priorität (haben sie die gleiche Priorität entscheide beliebig). Das Verfahren kann dann rekursiv wie folgt beschrieben werden:

1. Falls beide Bäume Distanz 0 haben, gebe sofort G zurück und überspringe die folgenden Schritte.
2. Falls G ein rechtes Kind mit Distanz 0 hat, setze K als rechtes Kind von G. Ansonsten verschmelze das rechte Kind von G mit K und setze den resultierenden Baum als rechtes Kind von G.
3. Falls nach Schritt 2 das rechte Kind von G größere Distanz hat als das linke Kind von G, vertausche die beiden Kinder.
4. Die neue Wurzel ist G. Die Distanz der neuen Wurzel ist 1 plus die Distanz des rechten Kindes.

Die Schritte garantieren nacheinander die Eigenschaften die in der Definition verlangt wurden für den resultierenden Linksbaum.

Einfügen (insert)

Um einen neuen Schlüssel einzufügen, schaffe einen neuen Knoten mit dem gewünschten Schlüssel und verschmelze den so neu entstandenen Linksbaum mit dem alten Baum. Der neu geschaffene Knoten soll vor dem verschmelzen zwei Linksbäume mit Distanz 0 als Kinder haben.

Extrahieren des nächsten Elements (extractMin)

Wegen der Heap-Eigenschaft ist der Schlüssel mit höchster Priorität jeweils an der Wurzel und er kann also direkt abgelesen werden. Die Kinder der Wurzel werden verschmolzen und das Resultat als neue Wurzel gesetzt. Diese Operation ist nur gültig, falls die Wurzel mindestens Distanz 1 hat.

Laufzeit

• Das Verschmelzen von zwei Linksbäumen mit insgesamt n Knoten mittels merge benötigt höchstens O(log n ) Zeit:

In jedem Schritt der Rekursion wird konstant viel Arbeit verrichtet. Jeder rekursive Aufruf erfolgt auf Bäumen, deren Distanzen in der Summe um genau eins kürzer sind. Die Rekursion endet spätestens wenn die Summe der Distanzen eins ist. Also ist die Laufzeit beschränkt durch die Summe der Distanzen. Da die Distanzen wegen der Definition von Linksbäumen die Länge des kürzesten Pfades bezeichnen, und die Länge des kürzesten Pfades in einem binären Baum mit k Knoten höchstens log ₂ (k) + 1 ist, folgt die Schranke.

• Die Laufzeit für insert und extractMin ist beschränkt durch eine Konstante plus die Zeit um zwei Linksbäume zu verschmelzen.

Literatur

• Thomas Ottman / Peter Widmayer: Algorithmen und Datenstrukturen. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg/Berlin 2002, ISBN 978-3-8274-1029-0 (Kapitel 6.1)