3.4 Treaps: Zufällige Einfüge-Reihenfolge simulieren

Wenn

n

Elemente in sortierter Reihenfolge eingefügt werden, dann entsteht ein "entarteter" Baum, der Tiefe

n - 1

. Wenn die Elemente in "zufälliger" Reihenfolge eingefügt werden, dann sieht der Baum "schön" aus. Das Phänomen kennen wir bereits von Quicksort.

In diesem Abschnitt lernen wir eine recht einfache Datenstruktur kennen, die unseren BST so aussehen lässt, als seien die Elemente in zufälliger Reihenfolge eingefügt worden, und erreicht damit eine effiziente Laufzeit beim Suchen, Einfügen und Löschen.

Gehen wir einen Schritt zurück. Ein Binärbaum ist entweder ein leerer Baum $◻$ oder besteht aus einem Wurzelknoten und zwei Teilbäumen:

So ein Binärbaum ist ein binärer Suchbaum (BST), wenn jeder innere Knoten (also der nicht ein Blatt ist) einen Schlüssel $x$ (auch Key genannt) enthält und alle Keys, die im linken Teilbaum $L$ vorkommen, kleiner als $x$ sind, und alle Keys, die im rechten Teilbaum $R$ vorkommen, größer als $x$ sind.

Übungsaufgabe 3.4.1 Wieviele BSTs gibt es für die Schlüsselmenge

{a, b, c}

? Zeichnen Sie alle!

Heaps

Definition 3.4.1 Sei

T

ein Binärbaum, in dem jeder innere Knoten

x

ein Gewicht

w_{x}

hat. Der Baum

T

ist ein Heap wenn jeder Elternknoten leichter ist als seine Kinder. Wenn also

y

ein innerer Knoten mit Elternknoten

x

ist, dann gilt

\begin{array}{r} w_{x} < w_{y} . \end{array}

Insbesondere hat die Wurzel das kleinste Gewicht aller inneren Knoten.

Zusätzlich verlangen wir in diesem Kapitel, dass alle Knoten unterschiedliche Gewichte haben.

Übungsaufgabe 3.4.2 Wieviele Heaps gibt es für die Gewichtemenge

{2, 5, 6}

? Zeichnen Sie alle!

Stellen Sie sich nun vor, wir hätten einen Binärbaum $T$ , in dem jeder innere Knoten u einen Schlüssel key(u) und auch ein Gewicht weight(u) hat. Wenn $T$ mit seinen Keys ein BST ist und gleichzeitig mit seeinen Keys ein Heap, dann nennen wir $T$ einen Treap. Das ist ein Kofferwort aus tree und heap. Im folgenden Beispiel sind die Keys die blauen Buchstaben und die Gewichte die roten Zahlen.

Übungsaufgabe 3.4.3 Zeichnen Sie einen Treap für die Menge

{(a, 84),
            (b, 29),
            (c, 95),
            (d, 47),
            (e, 12),
            (f, 86),
            (g, 17),
            (h, 94)}

Die blauen Buchstaben sind die Keys, die roten Zahlen sind die Gewichte.

Erklären Sie ihrem Sitznachbarn, wie Sie vorgegangen sind.

Übungsaufgabe 3.4.4 Gegeben sei eine Menge von Key-Weight-Paaren (k, w), in der kein Key und kein Gewicht doppelt vorkommen. Zeigen Sie, dass es genau einen Treap für diese Menge gibt.

Beobachtung 3.4.2 Wenn wir eine Menge

{(k_{1}, w_{1}), \dots, (k_{n}, w_{n})}

nach aufsteigenden

w_{i}

-Werten sortieren und in dieser Reihenfolge in einen anfangs leeren BST einfügen, dann entsteht ein Treap.

Suchen in einem Treap

Da Treaps Suchbäume in Bezug auf Ihre Keys sind, geht das Suchen genauso wie in BSTs.

Die Laufzeit von find ist proportional zur Tiefe des Knotens, der den gesuchte Key x enthält.

Übungsaufgabe 3.4.5 Was ich gerade geschrieben habe, ist nicht ganz korrekt. Wenn der Treap den Key x nicht enthält, wie können Sie dann die Laufzeit von find beschreiben?

Einfügen in einen Treap

Um ein neues Element in einen Treap einzufügen, gehen wir in zwei Phasen vor. In der ersten betrachten wir nur die Keys und fügen das neue Paar (x, w) ein wie in einen BST.

Das Problem ist, dass nach dieser Operation unser Baum zwar ein BST ist, aber möglicherweise kein Heap mehr: eventuell ist w zu schwer und wir müssen es nach oben treiben lassen. Dass wir es weiter nach unten sinken lassen müssen, kann nicht sein: nach dem BST-Einfügen ist (x, w) ein Blatt (bzw. hat zwei leere Teilbäume, je nachdem, ob Sie die Blätter zeichnen oder nicht).

In einer Phase lassen wir nun (x, w) nach oben treiben, solange das Gewicht kleiner ist als das des Elternknoten. Das ist aber komplizierter als in Heapsort, weil wir immer die BST-Bedingung mit im Kopf behalten müssen! Wir können also nicht einfach swap(u, parent(u)) aufrufen. Wir demonstrieren es an einem Beispiel.

Meiner Meinung nach ist in diesem Falle der Pseudo-Code aber tatsächlich leichter zu verstehen als das Beispiel.

Löschen aus einem Treap

In einem BST löschen wir einen Key , indem wir zuerst den Teilbaum finden, dessen Wurzelknoten enthält, und dann den Wurzelknoten mit dem Minimum des rechten Teilbaums (alternativ: dem Maximum des linken Teilbaums) vertauschen. Mit Treaps geht das nicht, weil dieser Knoten eventuell das falsche Gewicht hat. Wir gehen einen anderen Weg: wir lokalisieren den zu löschenden Knoten (x, w) und setzen dann sein Gewicht auf unendlich. Er ist nun also zu schwer für seine Position und muss nach unten sinken, bis er zu einem Blatt geworden ist. Dann können wir ihn ohne Probleme löschen. Der erste Teil, das Lokalisieren, geht wie für BSTs:

Die eigentliche Arbeit findet nun in delRoot statt. Wir gehen recht anders vor als für BSTs. Wir können nicht einfach das kleinste Element finden und an die Wurzel hochziehen, da das womöglich die Heap-Bedingung verletzt (Gewicht könnte zu groß sein). Nein, wir gehen anders, top-down vor. Falls ein Teilbaum der Wurzel leer ist, ist es einfach:

Ansonsten sieht die Lage so aus:

wobei ich in die Wurzel keine Buchstaben reinschreibe, weil die ja eh gelöscht werden soll. Als erstes müssen wir entscheiden, welcher Knoten die Wurzel des Ergebnis-Treaps ist. Entweder (y, v) oder (z, w), je nachdem, welcher davon "leichter" ist, wessen Gewicht also kleiner ist. Also:

Übungsaufgabe 3.4.6 Die Höhe eines Treaps ist, wie für jeden Baum, der maximale Abstand von Wurzel zu einem Blatt.

Finden Sie einen Treap und eine insert-Operation, die die Höhe reduziert!

Treap als randomisierte Datenstruktur und Programmierübung

Um Treaps zu einer "lieferfertigen" Datenstruktur zu machen, müssen wir festlegen, wie die Gewichte bestimmt werden. Sehen Sie, unsere "Kunden", also die User, die unseren Treap verwenden, wollen ja

treap.insert("dog")

schreiben und nicht

treap.insert("dog", 74)

Die Gewichte dienen ausschließlich der internen Organisation und sollen nicht von außen sichtbar sein. Also wählen wir für jedes neue Element ein zufälliges Gewicht, und zwar eine zufällige reelle Zahl zwischen 0 und 1. In Java-Syntax:

private void insert(A key, B value, double weight) { 
// many lines of code hidden here
}                        
public void insert(A key, B value) {
this.insert(key, value, Math.random());
}

Übungsaufgabe 3.4.7

Implementieren Sie mir einen BST. Die Programmiersprache dürfen Sie sich aussuchen. Da ich mich nicht durch hunderte Lines of Code wühlen will, geben Sie Ihrem Programm ein "User-Interface". Es soll einfache Befehle wie insert, find, delete von der Konsole lesen können und sich folgendermaßen bedienen lassen:

java BST # oder eben 'python BST.py'                             
insert dog Hund 
insert cat Katze 
insert bear Baer 
insert whale Wal 
insert wolf Wolf
find wolf 
true Wolf
find squid 
false
insert squid Tintenfisch
find dog
true Hund
find cat 
true Katze
delete dog 
find dog 
false

Wenn der Input zu Ende ist, soll das Programm terminieren. Achten Sie genau auf das Format, damit ich mit grep Ihren Output mit meinem (hoffentlich korrekten) Output vergleichen kann.

Wiederholen Sie alles, nun aber mit Treap. Das User-Interface soll identisch sein.

Schreiben Sie Ihren Namen als Kommentar in den Quelltext. Wir wollen ja dann einen "Sieger" verkünden.

Laufzeitanalyse

Definition 3.4.3

Sei eine Menge von Key-Weight-Paaren, in der kein Key und kein Schlüssel doppelt vorkommt. Für zwei Keys bezeichnen wir mit die Menge der Key-Weight-Paare für die oder gilt, wo also der Key zwischen und liegt.

Beispiel. Wenn {S = (a, 84), (b, 29), (c, 95), (d, 47), (e, 12), (f, 86), (g, 17), (h, 94)}, dann ist [e:b] = {(b, 29), (c, 95), (d, 47), (e, 12)}.

Theorem 3.4.4 Sei

eine Menge von Key-Weight-Paaren, in der kein Key und kein Schlüssel doppelt vorkommt. Sei

der Treap für

. Ein Element

ist ein Vorfahre von

im Treap

genau dann, wenn

das leichteste aller Elemente in

ist.

Beweis. Um eine Aussage der Form genau dann, wenn , oder als Formel

zu zeigen, müssen wir beide Richtungen zeigen, also

und

. In unserem Falle ist

ist Vorfahre von und

ist das leichteste Element in .

Die Richtung . Wir werden das Kontrapositiv beweisen, also . Wir nehmen an, dass kein Vorfahre von ist, und müssen nun ein Element in finden, das leichter ist als . Wir unterscheiden zwei Fälle.

1. Fall: ist ein Vorfahre von . Aus der Heap-Eigenschaft folgt nun, dass ist, und somit ist leichter als .
2. Fall: ist kein Vorfahre von . Nun ist nach Annahme weder Vorfahre von noch umgekehrt. Also haben sie einen gemeinsamen Vorfahren: . Da ein binärer Suchbaum ist, gilt und somit . Da ein Heap ist, gilt , also ist leichter als .

In beiden Fällen haben wir ein leichteres Element in

gefunden.

Die Richtung . Wir zeigen wiederum das Kontrapositiv . Wir nehmen also an, dass nicht das leichteste Element in ist und müssen nun zeigen, dass kein Vorfahre von ist. Sei nun also das leichteste Element in . Es ist nicht ausgeschlossen, dass ist, a allerdings gilt nach Annahme .

Wir bauen nun den Treap, in dem wir die Elemente von leicht nach schwer sortiert in einen BST einfügen. Wir pausieren, nachdem eingefügt worden ist. Sei der nun entstandene Treap, und sei der Pfad von der Wurzel bis zum Elternknoten von . Kein Element auf ist in , also sind alle Keys in entweder kleiner als oder größer als . Das heißt: jedes weitere Element aus , dass wir nach der "Pause" einfügen, wird zuerst den Pfad entlanglaufen, bei ankommen, und dann entweder zum linken oder zum rechten Kind von weitergeschickt. Das Element landet im linken Teilbaum von , weil ja gilt. Das Element landet im rechten Teilbaum oder ist selbst. In beiden Fällen ist kein Vorfahre von .

Wir haben nun beide Richtungen gezeigt.

Wir führen nun etwas Notation ein. Sei die Menge der Schlüssel-Wert-Paare im Treap und die Menge der Schlüssel. Für einen Schlüssel bezeichnen wir mit sein Gewicht, also das (eindeutige) , für das gilt. Für zwei Schlüssel definieren wir

Wir demonstrieren anhand mehrerer Beispiele, wie , der Treap für und die Werte zusammenhängen. Im folgenden Stellen wir als -Matrix dar (wobei wir aber die Stellen, die 0 sind, einfach leer lassen).

Beobachtung 3.4.5 Die Tiefe

eines Elements

im Treap

folgt der Formel

also der Anzahl der Einsen in der Spalte, die zu

gehört. Hier schreiben wir

, da die rechte Seite die Anzahl der Knoten auf dem Pfad zu

zählt, nicht die Anzahl der Kanten.

Die Anzahl der Einsen in der Zeile von ist die Anzahl der inneren Knoten im Unterbaum von .

Wenn wir nun die Gewichte zufällig wählen, dann werden Treap und die obige Matrix zu Zufallsvariablen, sie nehmen also je nach konkretem Ausgang des Zufallsexperiments verschiedene Gestalt an. Somit varriert auch von Experiment zu Experiment. Uns interessiert der Erwartungswert, wie weit also im Schnitt von der Wurzel des Treaps entfernt ist. Fragen wir uns nun, was denn die Matrix im Erwartungswert für eine Gestalt annimmt. Fokusieren wir auf zwei konkrete Schlüssel . Nach dem obigen Theorem nimmt den Wert 1 genau dann an, wenn das leichteste aller Elemente in ist. Mit welcher Wahrscheinlichkeit geschieht dies? Nun, alle Gewichte sind zufällig, und eines der Elemente in muss schließlich das Leichteste sein; jedes Element ist mit gleicher Wahrscheinlich das Leichteste. Also ist mit Wahrscheinlichkeit gleich 1.

Lemma 3.4.6 Der Erwartungswert von

ist

Und somit schaut die Matrix

im Erwartungswert so aus:

Die erwartete Tiefe des kleinsten Schlüssels (und auch des größten Schlüssels) ergibt sich daher nach der Formel

Die obige Summe hat einen Namen: die harmonische Zahl . Wir kennen zwar keine "explizite" Formel dafür, werden aber weiter unten eine recht präzise Abschätzung zeigen. Für Schlüssel, die mehr "in der Mitte" kommen, ist die Formel für die erwartete Tiefe etwas komplizierter.

Theorem 3.4.7 Sei

der

-kleinste Schlüssel, so dass es also genau

kleinere und genau

größere Schlüssel gibt. Dann gilt

Als nächstes zeigen wir eine präzise Abschätzung für :

Lemma 3.4.8

Beweis.

In der oberen Abbildung sehen Sie den Graph der Funktion in blau; die Fläche unterhalb der Kurve zwischen und ist Die roten Balken haben eine Fläche von ; da alle roten Balken unterhalb der blauen Kurve liegen, folgern wir Um eine obere Schranke herzuleiten, finden wir Balken, die die blaue Kurve von oben einschränken:

Die violetten Balken haben eine Gesamtfläche von

; ihre Oberkanten liegen allesamt oberhalb der blauen Kurve, und daher gilt

Theorem 3.4.9 Die Operationen find,insert,delete in einem Treap haben erwartete Laufzeit

Beweis. Von der Funktionsweise von find,insert,delete ist klar, dass die Laufzeit höchstens proportional zur Tiefe des Baumes ist; die Tiefe des Baumes ist die maximale Tiefe aller Knoten, also

. Zwar gilt in der Tat

, allerdings ist dies ein wenig komplizierter. Was wir oben bewiesen haben, ist dass die erwartete Tiefe eines einzelnen Elements

höchstens

. Dies ist aber ausreichend, um die Laufzeitschranke zu zeigen.

find x. Falls , dann ist die Laufzeit von find proportional zu , was im Erwartungswert höchstens ist. Schwieriger wird es, wenn . Dann wird find in jedem Fall bis zu einem Blatt von laufen und dann null bzw. Nothing zurückliefern. Wie können wir die Tiefe dieses Blattes beschränken? Seien der größte Schlüssel mit und der kleinste Schlüssel mit . Wir erkennen, dass der letzte innere Knoten, den find x besucht, entweder der Knoten von oder ist. Die erwartete Anzahl der besuchten inneren Knoten ist also Ein Maximum zweier Zufallsvariablen abzuschätzen ist nicht immer einfach. Wir behelfen uns mit einem Trick: , und daher gilt
insert x. Beim Einfügen plazieren wir erst einmal an einem Blatt von , so als wäre nur ein BST und kein Treap. Dann lassen wir mittels Rechts- oder Linksrotationen hochsteigen, bis es seinen richtigen Platz gefunden haben wird. Sei die Tiefe von im resultierenden Treap. Sei die Tiefe, die eingenommen hat, als wir es als Blatt eingefügt haben, bevor wir also die Rotationen durchgeführt haben. Dies beschreibt auch die Laufzeit dieser ersten Phase. In Phase zwei schieben wir pro Rotationen eine Ebene nach oben, also führen wir Rotationen aus; die Gesamtlaufzeit ist also proportional zu . Wir wissen bereits, dass ist, weil das ja die Tiefe von im wiederhergestellten Treap ist. Wie steht es um , die Anzahl der Rotationen? Hier verwende ich eine wohl recht suboptimale Abschätzung: bei jeder Rotation gewinnt der an hängende Unterbaum einen weiteren Knoten hinzu, gewinnt also einen weiteren Nachkommen. Daher ist höchstens die Anzahl der Knoten im Unterbaum von , also und ist daher im Erwartungswert genau die Tiefe von . Wir folgern:
delete x. Dies führt zu allererst die gleichen Schritte aus die find x, also viele; sobald es in lokalisiert hat, ruft es deleteRoot am entsprechenden Unterbaum auf. Dies führt eine Reihe von Rotationen aus, um nach unten zu bewegen, bis eines seiner Kinder ein Blatt ist. In jeder Rotation nimmt die Anzahl der Nachkommen von ab; hatte anfangs also mindestens Nachfahren (sich selbst eingeschlossen, daher die ), und somit ist Wir folgern, dass auch delete x höchstens Schritte durchführt.