4.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 \(\square\) 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 Wieviele BSTs gibt es für die Schlüsselmenge \(\{a,b,c\}\)? Zeichnen Sie alle!

Heaps

Definition 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{align*} w_x \lt w_y \ . \end{align*} Insbesondere hat die Wurzel das kleinste Gewicht aller inneren Knoten.

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

Übungsaufgabe 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 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 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 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 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 \(\square\) 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 \(x\), indem wir zuerst den Teilbaum finden, dessen Wurzelknoten \(x\) 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 \(R\) 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 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

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

Sei \(S = \{(x_1, w_1), \dots, (x_n,w_n)\}\) eine Menge von Key-Weight-Paaren, in der kein Key und kein Schlüssel doppelt vorkommt. Für zwei Keys \(x, y\) bezeichnen wir mit \([x:y]\) die Menge der Key-Weight-Paare \((k,w) \in S\) für die \(x \leq k \leq y\) oder \(y \leq k \leq x\) gilt, wo also der Key \(k\) zwischen \(x\) und \(y\) 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 Sei \(S = \{(x_1, w_1), \dots, (x_n,w_n)\}\) eine Menge von Key-Weight-Paaren, in der kein Key und kein Schlüssel doppelt vorkommt. Sei \(T\) der Treap für \(S\). Ein Element \((x,u)\) ist ein Vorfahre von \((z,w)\) im Treap \(T\) genau dann, wenn \((x,u)\) das leichteste aller Elemente in \([x:z]\) ist.

Beweis. Um eine Aussage der Form \(A\) genau dann, wenn \(B\), oder als Formel \(A \Longleftrightarrow B\) zu zeigen, müssen wir beide Richtungen zeigen, also \(A \Longrightarrow B\) und \(A \Longleftarrow B\). In unserem Falle ist \(A := \) \(x\) ist Vorfahre von \(y\) und \(B := \) \((x,u)\) ist das leichteste Element in \([x:z]\).

Die Richtung \(A \Longleftarrow B\). Wir werden das Kontrapositiv beweisen, also \(\neg A \Longrightarrow \neg B\). Wir nehmen an, dass \((x,u)\) kein Vorfahre von \((z,w)\) ist, und müssen nun ein Element in \([x:z]\) finden, das leichter ist als \((x,u)\). Wir unterscheiden zwei Fälle.

1. Fall: \(z\) ist ein Vorfahre von \(x\). Aus der Heap-Eigenschaft folgt nun, dass \(w \lt u\) ist, und somit ist \( (z,w)\) leichter als \( (x,u)\).
2. Fall: \(z\) ist kein Vorfahre von \(x\). Nun ist nach Annahme weder \(x\) Vorfahre von \(z\) noch umgekehrt. Also haben sie einen gemeinsamen Vorfahren: \( (y,v)\). Da \(T\) ein binärer Suchbaum ist, gilt \(x \lt y \lt z\) und somit \( (y,v) \in [x:z]\). Da \(T\) ein Heap ist, gilt \(v \lt u\), also ist \((y,v)\) leichter als \((x,u)\).

In beiden Fällen haben wir ein leichteres Element in \([x:y]\) gefunden.

Die Richtung \(A \Longrightarrow B\). Wir zeigen wiederum das Kontrapositiv \(\neg B \Longrightarrow \neg \A\). Wir nehmen also an, dass \((x,u)\) nicht das leichteste Element in \([x:z]\) ist und müssen nun zeigen, dass \(x\) kein Vorfahre von \(z\) ist. Sei nun also \((y,v)\) das leichteste Element in \([x:z]\). Es ist nicht ausgeschlossen, dass \((y,v) = (z,w)\) ist, a allerdings gilt nach Annahme \((y,v) \ne (x,u)\).

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

Wir haben nun beide Richtungen gezeigt. \(\square\)

Wir führen nun etwas Notation ein. Sei \(S = \{(x_1, w_1), \dots, (x_n,w_n)\}\) die Menge der Schlüssel-Wert-Paare im Treap \(T\) und \(K = \{x_1,\dots,x_n\}\) die Menge der Schlüssel. Für einen Schlüssel \(x \in K\) bezeichnen wir mit \(w(x)\) sein Gewicht, also das (eindeutige) \(w\), für das \((x,w)\in S\) gilt. Für zwei Schlüssel \(x,y\) definieren wir

\begin{align*} I_{x,y} := \begin{cases} 1 & \textnormal{ wenn \(x\) ein Vorfahre von \(y\) ist, }\\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}

Wir demonstrieren anhand mehrerer Beispiele, wie \(S\), der Treap für \(S\) und die Werte \(I_{x,y}\) zusammenhängen. Im folgenden Stellen wir \(I_{x,y}\) als \((n \times n)\)-Matrix \(I\) dar (wobei wir aber die Stellen, die 0 sind, einfach leer lassen).

Beobachtung Die Tiefe \(\depth(x,T)\) eines Elements \(x\) im Treap \(T\) folgt der Formel \begin{align*} \depth(x,T) + 1 & = \sum_{y} I_{y,x} \ , \end{align*} also der Anzahl der Einsen in der Spalte, die zu \(x\) gehört. Hier schreiben wir \(\depth(x,T)+1\), da die rechte Seite die Anzahl der Knoten auf dem Pfad zu \(x\) zählt, nicht die Anzahl der Kanten.

Die Anzahl der Einsen in der Zeile von \(x\) ist die Anzahl der inneren Knoten im Unterbaum von \(x\).

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 \(\depth(x,T)\) von Experiment zu Experiment. Uns interessiert der Erwartungswert, wie weit \(x\) also im Schnitt von der Wurzel des Treaps entfernt ist. Fragen wir uns nun, was denn die Matrix \(I\) im Erwartungswert für eine Gestalt annimmt. Fokusieren wir auf zwei konkrete Schlüssel \(x, y\). Nach dem obigen Theorem nimmt \(I_{x,y}\) den Wert 1 genau dann an, wenn \(x\) das leichteste aller Elemente in \([x:y]\) ist. Mit welcher Wahrscheinlichkeit geschieht dies? Nun, alle Gewichte sind zufällig, und eines der Elemente in \([x:y]\) muss schließlich das Leichteste sein; jedes Element ist mit gleicher Wahrscheinlich das Leichteste. Also ist \(I_{x,y}\) mit Wahrscheinlichkeit \(\frac{1}{|[x:y]}\) gleich 1.

Lemma Der Erwartungswert von \(I_{x,y}\) ist \begin{align*} \mathbb{E}[I_{x,y}] = \frac{1}{|[x:y]|} \ . \end{align*}

Und somit schaut die Matrix \(I\) im Erwartungswert so aus:

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

\begin{align*} \mathbb{E}[\depth(a,T)+1] = 1+ \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = H_n \ . \end{align*}

Die obige Summe hat einen Namen: die harmonische Zahl \(H_n\). 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 Sei \(x \in K\) der \(k\)-kleinste Schlüssel, so dass es also genau \(k-1\) kleinere und genau \(n-k\) größere Schlüssel gibt. Dann gilt \begin{align*} \mathbb{E}[\depth(x,T)+1] & = 1 + (\frac{1}{2} + \cdots + \frac{1}{k}) + (\frac{1}{2} + \cdots + \frac{1}{n-k+1}) \\ & = H_{k} + H_{n-k+1} - 1 \\ & \leq 2\, H_n - 1 \ . \end{align*}

Als nächstes zeigen wir eine präzise Abschätzung für \(H_n\):

Lemma \(\ln(n) + \frac{1}{n} \leq H(n) \leq \ln(n)+1\).

Beweis.

In der oberen Abbildung sehen Sie den Graph der Funktion \(x \mapsto \frac{1}{x}\) in blau; die Fläche unterhalb der Kurve zwischen \(x=1\) und \(x=n\) ist \begin{align*} \int_1^n \frac{1}{x} dx = \ln(n) \ . \end{align*} Die roten Balken haben eine Fläche von \(H_n-1\); da alle roten Balken unterhalb der blauen Kurve liegen, folgern wir \begin{align*} H_n - 1 \leq \ln(n) \ . \end{align*} Um eine obere Schranke herzuleiten, finden wir Balken, die die blaue Kurve von oben einschränken:

Die violetten Balken haben eine Gesamtfläche von \(H_n - \frac{1}{n}\); ihre Oberkanten liegen allesamt oberhalb der blauen Kurve, und daher gilt \begin{align*} \ln(n) \leq H_n - \frac{1}{n} \ . \end{align*} \(\square\)

Theorem Die Operationen find,insert,delete in einem Treap haben erwartete Laufzeit \(O(\log n)\).

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 \(\max_{x} \depth(x,T)\). Zwar gilt in der Tat \(\depth(T) \in O(\log n)\), allerdings ist dies ein wenig komplizierter. Was wir oben bewiesen haben, ist dass die erwartete Tiefe eines einzelnen Elements \(x\) höchstens \(2H_n - 1\). Dies ist aber ausreichend, um die Laufzeitschranke zu zeigen.

find x. Falls \(x \in K\), dann ist die Laufzeit von find proportional zu \(\depth(x,T)\), was im Erwartungswert höchstens \(2H_n-1 \in O(\log n)\) ist. Schwieriger wird es, wenn \(x \not \in K\). Dann wird find in jedem Fall bis zu einem Blatt von \(T\) laufen und dann null bzw. Nothing zurückliefern. Wie können wir die Tiefe dieses Blattes beschränken? Seien \(y \in K\) der größte Schlüssel mit \(y \lt x\) und \(z \in K\) der kleinste Schlüssel mit \(z \gt x\). Wir erkennen, dass der letzte innere Knoten, den find x besucht, entweder der Knoten von \(y\) oder \(z\) ist. Die erwartete Anzahl der besuchten inneren Knoten ist also \begin{align*} \mathbb{E}[\max (\depth(y,T), \depth(z,T))] \ . \end{align*} Ein Maximum zweier Zufallsvariablen abzuschätzen ist nicht immer einfach. Wir behelfen uns mit einem Trick: \(max (a,b) \leq a + b\), und daher gilt \begin{align*} \mathbb{E}[\max (\depth(y,T), \depth(z,T))] & \leq \E[\depth(y,T) + \depth(z,T)] \leq 4 H_n - 2 \in O(\log n) \ . \end{align*}
insert x. Beim Einfügen plazieren wir \(x\) erst einmal an einem Blatt von \(T\), so als wäre \(T\) nur ein BST und kein Treap. Dann lassen wir \(x\) mittels Rechts- oder Linksrotationen hochsteigen, bis es seinen richtigen Platz gefunden haben wird. Sei \(d := \depth(x,T)\) die Tiefe von \(x\) im resultierenden Treap. Sei \(t\) die Tiefe, die \(x\) 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 \(x\) eine Ebene nach oben, also führen wir \(r := t-d\) Rotationen aus; die Gesamtlaufzeit ist also proportional zu \(t + t - d = d + 2r\). Wir wissen bereits, dass \(E[d] \in O(\log n)\) ist, weil das ja die Tiefe von \(x\) im wiederhergestellten Treap \(T\) ist. Wie steht es um \(r\), die Anzahl der Rotationen? Hier verwende ich eine wohl recht suboptimale Abschätzung: bei jeder Rotation gewinnt der an \(x\) hängende Unterbaum einen weiteren Knoten hinzu, \(x\) gewinnt also einen weiteren Nachkommen. Daher ist \(r+1\) höchstens die Anzahl der Knoten im Unterbaum von \(x\), also \begin{align*} r+1 = \sum_{y} I_{x,y} \ , \end{align*} und ist daher im Erwartungswert genau die Tiefe von \(x\). Wir folgern: \begin{align*} \E[d + 2r] = \E[3d] \in O(\log n)\ . \end{align*}
delete x. Dies führt zu allererst die gleichen Schritte aus die find x, also \(O(\log n)\) viele; sobald es \(x\) in \(T\) lokalisiert hat, ruft es deleteRoot am entsprechenden Unterbaum auf. Dies führt eine Reihe von \(r\) Rotationen aus, um \(x\) nach unten zu bewegen, bis eines seiner Kinder ein Blatt ist. In jeder Rotation nimmt die Anzahl der Nachkommen von \(x\) ab; \(x\) hatte anfangs also mindestens \(r+1\) Nachfahren (sich selbst eingeschlossen, daher die \(+1\)), und somit ist \begin{align*} r+1 \leq \sum_{y} I_{x,y} \ . \end{align*} Wir folgern, dass auch delete x höchstens \(O(\log n)\) Schritte durchführt.

\(\square\)