Sortieren und Suchen

Geschrieben von Daniel Graf.

Dieser Vortrag erklärt dir die Algorithmen und Datenstrukturen die hinter std::sort, std::priority_queue und std::set stecken, sodass du die wichtigsten Ideen verstehst, weisst warum sie so schnell sind wie sie sind und sie auch selber implementieren kannst. Auch wenn du für viele SOI-Aufgaben die std-Tools einfach benützen kannst, lohnt es sich manchmal doch zu wissen, wie es eigentlich funktioniert.

\(\newcommand{\N}{\mathbb{N}} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\O}{\mathcal{O}}\)

(Diese Vorlesungsnotizen basieren mehrheitlich auf meiner Vorlesungsmitschrift zu “Datenstrukturen und Algorithmen” von Prof. Peter Widmayer an der ETH Zürich im Frühling 2016.)

Sortieren

Wie wir Datenmengen ordnen, oder eben sortieren, schauen wir uns zuerst an.

Es gibt Leute, die sagen, dass Sortieren für mehr als 90% der weltweit aufgewendeten Rechnerzeit verantwortlich ist. Das ist vielleicht ein wenig übertrieben, aber Sortieren ist ein sehr wichtiges und häufiges Problem.

Will man einen Datensatz sortieren, so kann man die einzelnen Daten vergleichen. Handelt es sich beispielsweise um eine Menge von Mails, die man chronologisch sortieren will, so vergleicht man nicht zwei vollständige Mails, sondern betrachtet nur das Datum. Der Teil des Datensatzes, den man für das Sortieren verwendet, nennt man Schlüssel.

Wenn man die Effizienz eines Sortieralgorithmus analysiert, betrachtet man die Anzahl Schlüsselvergleiche, die ein Sortieralgorithmus durchführt. Je mehr Schlüsselvergleiche durchgeführt werden, desto schlechter bzw. langsamer läuft eine Sortieralgorithmus. Zusätzlich ist für die Effizienz auch die Anzahl der Bewegungen (z.B. Vertauschung zweier Elemente) von Daten wichtig.

Sortieren überprüfen

Zuerst muss das Ziel klar sein: Wie erkennen wir ob ein Array sortiert ist? Das Array heisse \(A\) und sei indexiert von \(1\) bis \(n\). Wir können das Prüfen mit einer simplen Schleife umsetzen.

Prüfe(A):
    for i = 1 to n-1 do
        if A[i] > A[i+1] then
            ALARM
    falls nie ALARM: OK

Diese Überprüfung braucht nur maximal \(n-1\) Vergleiche und kostet also \(\O(n)\) Vergleiche, \(\O(n)\) Zeit und \(\O(1)\) Extraplatz.

Bubblesort

Idee

Jetzt wollen wir aber nicht nur prüfen sondern auch selber sortieren. Dazu soll uns der Prüf-Algorithmus als Vorlage dienen. Denn sobald wir abbrechen beim Prüfen, wissen wir zwei Elemente, die wir vertauschen sollten.

for i:=1 to n-1 do
    if A[i] > A[i+1] then
        tausche A[i] mit A[i+1]

Das alleine genügt noch nicht. Die Sequenz 453 wird zu 435 ist also noch nicht sortiert. Also ist ein einziger solcher Durchlauf noch nicht genug. Darum wiederholen wir diesen Loop mehrmals, so lange bis sich nichts mehr ändert. Wie lange geht das? Behauptung: Nach höchstens \(n-1\) Wiederholungen ist der Array sortiert. Idee: Nach dem ersten Durchlauf steht das grösste Element an der Stelle ganz rechts und wird nachher nie mehr verschoben. Damit ist nach dem zweiten Durchlauf das zweitgrössten Element an der korrekten Stelle usw. Nach \(n-1\) Durchläufen sind somit alle Schlüssel am korrekten Platz.

Da die Schlüssel hier Runde für Runde an den korrekten Ort “blubbern”, nennt man dieses Verfahren Bubblesort.

Analyse

Wir können frühzeitig abbrechen, wenn sich in einer Runde nichts mehr ändert.

BubbleSort(A)
    for j:=1 to n-1 do
        kleiner_alarm := Nein
        for i:=1 to n-1 do
            if A[i] > A[i+1] then
                kleiner_alarm := Ja
                tausche A[i] mit A[i+1]
        if kleiner_alarm = Nein
            STOP

Bringt diese Abbruchbedingung immer etwas? [1]

Bis jetzt haben wir jeweils nur auf die Anzahl Schlüsselvergleiche und auf den Extra-Platz geschaut. Was auch relevant ist, ist die Anzahl Bewegungen von Datensätzen.

Der schlimmste Fall ist die absteigend sortierte Folge als Eingabe. Dann benötigen wir \(\Theta(n^2)\) Vertauschungen und Bewegungen.

Für einen bereits sortierten Array sind wir schon nach einer einzigen Schleife fertig, wenn wir Bubble-Sort klug implementiert haben. Wir können also davon profitieren, dass \(A\) bereits vorsortiert ist.

Sortieren durch Auswahl (Selection Sort)

Idee

Wir wollen nun unser Lieblingsverfahren zum Algorithmenentwurf bemühen, die Induktion. Wir nehmen als Invariante, dass wir nach dem \(i\)-ten Schritt die ersten \(i\) Elemente des Arrays sortiert sind und wir diese Elemente nie mehr verschieben müssen (Präfix ist “fix fertig”). Um diese Invariante aufrecht zu erhalten, fügen wir in jedem Schritt das Minimum des noch unsortierten rechten Teils ans Ende des sortierten linken Teils, also

| sortierter Teil | i | unsortierter, aber grösserer Teil |

Als Pseudocode:

SelectionSort(A)
    for i = 1 to n-1
        j = Index des Minimums im Bereich i bis n
        tausche A[i], A[j]

Analyse

Um das Maximum zu finden brauchen wir \(i-1\) Vergleiche. Somit beläuft sich die Anzahl Vergleiche wieder auf die arithmetische Reihe \(\sum_{i=1}^{n-1}(i-1) \in \Theta(n^2)\).

Laufzeit: \(\Theta(n^2)\) Vergleiche, \(\O(n)\) Tauschoperationen, daher Zeit \(\O(n^2)\). Extraplatz: \(\O(1)\).

Gegenüber Bubblesort haben wir also in der Laufzeit nichts gewonnen, aber immerhin führen wir nur noch linear viele Vertauschungen durch. Die quadratische Anzahl Vergleiche gefällt uns noch nicht. Hilft uns hier eine andere Invariante?

Sortieren durch Einsetzen (Insertion Sort)

Nehmen wir als Invariante, dass das Präfix der Länge \(i\) sortiert ist, aber nicht dass die Elemente bereits an ihrem finalen Platz sind. Diese Invariante können wir aufrecht erhalten, indem wir das neue Element einfach an der korrekten Stelle ins bisherige Teilarray einsortieren.

[1 2 7 9 | 4 | Rest] -> [1 2 4 7 9 | Rest]

Wie finden wir den Ort, wo das neue Element eingefügt werden sollte? Wir können die Position mit binärer Suche finden: \(\O(\log n)\) Vergleiche. Dann nehmen wir das Teilstück, das einen Platz nach rechts muss, und schieben es Element für Element um eine Position nach rechts: \(\O(n)\) Tauschoperationen.

InsertionSort(A)
    for i = 2 to n do
        suche binär nach A[i] im Bereich 1,..,i-1
            -> sei dies Position k
        verschiebe A[k,..,i-1] nach A[k+1,..,i]
        setze das alte A[i] nach A[k]

Total: \(\O(n \log n)\) Vergleiche und \(\Theta(n^2)\) Tauschoperationen (Bewegungen) und daher \(\Theta(n^2)\) Laufzeit [2].

Können wir diese vielen Vertauschungen umgehen, indem wir, anstatt eines Arrays, eine linear verkettete Liste benutzen? Weil dann könnten wir ja durch das Umbiegen zweier Zeiger ein neues Element einfügen. Das Problem: Auf einer verlinkten Liste können wir nicht binär suchen.

Bis jetzt haben wir noch keinen Algorithmus, der schneller ist als quadratische Zeit. Aber es besteht Hoffnung: Wir haben ein Verfahren mit linear vielen Bewegungen und eines mit \(\O(n \log n)\) Vergleichen. Gelingt es uns das beste aus diesen zwei Welten zu kombinieren?

Wie macht man das? Das Problem bis jetzt war, dass wir jeweils viel Aufwand (lineare Zeit) betreiben mussten, um ein neues Element zu unserer Invariante hinzuzufügen. Versuchen wir unsere Invariante etwas aufzuweichen, sodass dies schneller geht.

Heapsort

Idee

Wir wollen uns vom Sortieren durch Auswahl inspirieren lassen, dabei aber versuchen das Auswählen ohne die linear vielen Vergleiche hinzubekommen. Wir wollen dazu dem noch unsortierten Teil des Array ein bisschen Ordnung aufdrücken, ihn also weder komplett unsortiert zu lassen noch komplett zu sortieren.

Wir stellen uns dazu vor, dass die Zahlen in A einen Binärbaum darstellen. Dabei sollen alle bis auf das letzte Niveau des Baumes voll sein. Das letzte Niveau füllen wir von links nach rechts.

  Wurzel
    5 Vater      A: 1 2 3 4 5 6
   / \              5 7 1 6 4 2
  7   1 Kind
 / \ /
6  4 2
Blätter

Das können wir implizit machen. Die beiden Kinder von Knoten \(i\), stehen an Position \(2i\) und \(2i+1\). Und der Vater von Knoten i steht an \(\lf i/2 \rf\).

Warum ist dies eine nützliche Idee? Weil diese Baumstruktur nur eine geringe Höhe hat. Bei den Rechnungen der Binären Suche haben wir gesehen, dass wir mit einem Baum der Höhe \(\log(n)\) schon \(n\) Elemente unterbringen können. Wenn wir also auf diesen Niveaus des Baumes operieren können, dann können wir uns vielleicht Laufzeiten von \(\log(n)\) pro Operation erhoffen.

Im Moment haben die Elemente im Baum aber noch keinerlei Struktur. Wir wollen also etwas Struktur verlangen, aber auch nicht zu viel, sonst wird es wieder linear. Was wir verlangen wollen: Für jede Eltern-Kind Beziehung, soll das grössere Element oben stehen. Der Wert im Elternknoten soll also immer grösser sein als der Wert im Kinderknoten. Dies nennt man die Heap-Bedingung.

Nehmen wir mal kurz an, dass die Eingabe “per Zufall” schon die Heapbedingung erfüllt, zum Beispiel so:

  Wurzel
    7       A: 1 2 3 4 5 6
   / \         7 6 4 5 1 2
  6   4
 / \ /
5  1 2
Blätter

Jetzt wollen wir die sortierte Folge schrittweise aus diesem Heap extrahieren. Wir können schnell herausfinden, was das letzte Element der sortierten Folge ist, denn das grösste Element muss an der Wurzel des Heaps stehen. Tauschen wir also die \(2\) mit der \(7\) aus.

    2       A: 1 2 3 4 5 6
   / \         2 6 4 5 1|7
  6   4
 / \ X
5  1 7

Nun zwacken wir die \(7\) ab und nehmen an, dass sie nicht mehr Teil vom Heap ist. Um induktiv argumentieren zu können, wäre es gut, wenn der Rest (also die ersten \(6\) Elemente) wieder einen Heap bilden würden. Da nun aber die \(2\) an der Wurzel steht, ist die Heapbedingung dort verletzt. Wir können die Heap-Bedingung aber leicht wieder herstellen, indem wir die neue Wurzel “versickern” lassen. Dazu schauen wir die beiden Kinder von \(2\) an und nehmen das grössere Element nach oben:

    6       A: 1 2 3 4 5 6
   / \         6 2 4 5 1|7
  2   4
 / \ X
5  1 7

Jetzt stimmt die Heap-Bedingung an der Wurzel wieder, aber die \(2\) sollte auch noch mit der \(5\) die Plätze tauschen, also weiter versickern.

    6       A: 1 2 3 4 5 6
   / \         6 5 4 2 1|7
  5   4
 / \ X
2  1 7

Jetzt haben wir wieder einen Heap und - oh Wunder - das global zweitgrösste Element steht nun an der Wurzel. Also vertauschen wir die \(6\) mit der \(1\), zwacken die \(6\) ab und lassen die \(1\) versickern.

    1       A: 1 2 3 4 5 6
   / \         1 5 4 2|6 7
  5   4
 / X X
2  6 7

    5       A: 1 2 3 4 5 6
   / \         5 1 4 2|6 7
  1   4
 / X X
2  6 7

    5       A: 1 2 3 4 5 6
   / \         5 2 4 1|6 7
  2   4
 / X X
1  6 7

Pseudocode und Details

Heapsort(A)
    bilde einen Heap aus der Eingabe
    for i := n to 2
        tausche A[1] mit A[i]
        versickere A[1] im Bereich A[1 .. i-1]

Was noch fehlt: Wie bilden wir einen solchen Heap? Induktiv: Nehmen wir an wir hätten schon zwei kleine Heaps und wollen ein neues Element als Wurzel der beiden hinzufügen und danach einen grossen Heap daraus erstellen. Genau dies, leistet die Funktion versickere.

   x
  / \
H1   H2

Machen wir die versickere-Funktion noch explizit:

versickere(i,j)
    // Versickere Schlüssel an Position i
    // in einem Heap der ersten j Elemente
    if 2i < j then // Falls i noch Kinder hat.
        max = 2*i
        if 2i + 1 <= j then // Gibt es ein rechtes Kind?
            if A[2i+1] > A[2i] then // Welches Kind ist das Grössere?
                max = 2i+1
        if A[max] > A[i] then
            // Falls das grössere Kind grösser ist als A[i]
            tausche (max, i)
            versickere(max,j)
            // lassen wir das getauschte
            // Element weiter versickern.
    // Sonst sind wir fertig.

Nun müssen wir uns noch um die initiale Heapherstellung kümmern. Wir machen dazu Induktion von unten, um auch zum Bauen des Heaps wiederholt zwei kleinere Heaps zusammenzufügen. Dabei sind alle Blätter für sich alleine genommen bereits korrekte kleine Heaps. Wenn wir danach die Positionen \(i\) von \(\frac{n}{2}\) bis \(1\) der Reihe nach runter gehen, dann haben wir jeweils einen neuen Knoten \(i\) mit zwei Teilbäumen bei \(2i\) und \(2i+1\) darunter, die bereits die Heapbedingung erfüllen. Ein einzelnes versickere(i,n) stellt daher die Heapbedingung für den ganzen Baum an Position \(i\) her.

Wie verwenden wir also dieses versickere nun genau?

Heapsort(A)
    // Heap aufbauen
    for i := n/2 down to 1
        versickere(i,n)
    // Wiederholt das Maximum ans Ende tauschen
    // und den Heap reparieren.
    for i := n down to 2
        tausche A[1] mit A[i]
        versickere(1,i-1)

Analyse

Wieviele Vergleiche machen wir?

Das versickere läuft quasi einfach einem Pfad dem Baum entlang, sieht also höchstens \(log(n)\) Niveaus. Auf jedem Niveau müssen wir bis zu zwei Schlüsselvergleiche machen. Somit machen wir rund \(2\log n\) Vergleiche pro versickere.

Somit machen wir insgesamt \(2 n \log(n)\) Vergleiche (ohne den Heap zu bauen). Dies absolut ohne Extraplatz! Ein Wermutstropfen (z.B. gegenüber dem Mergesort, das wir evtl. noch sehen werden) ist der Faktor \(2\), dazu unten mehr.

Wieviele Bewegungen machen wir? Entlang eines Versickerpfades machen wir maximal \(\log n\) Vertauschungen. Somit ist die Anzahl Bewegungen auch in \(\O(n \log n)\).

Wieviel kommt noch dazu beim Bauen des Heaps? Wir rufen versickern \(\frac{n}{2}\) mal auf, also höchstens \(\O(n\log n)\). Wenn man genauer hinschaut, kann man gar zeigen, dass es nur \(\O(n)\) ist.

Total: \(\O(n \log n)\) Vergleiche und Bewegungen.

Einfügen

Um alle Operationen einen Priority Queue, nämlich “Maximum extrahieren” (aus einem Max-Heap) und “Einfügen eines neuen Elementes” zu unterstützen, fehlt uns noch das Einfügen. Das ist ganz einfach: Wir vergrössern den Array um eine Position, schreiben dort das neue Element hin und stellen danach die Heapbedingung wieder her indem wir das Element so lange wie nötig “hochblubbern” lassen.

Einfügen(x)
    // Neues Element anhängen:
    n := n+1
    A[n] = x
    // Hochblubbern lassen:
    i := n
    while i > 1 and A[i/2] < A[i]
        swap(A[i/2], A[i])
        i := i/2

Das Einfügen dauert also höchstens so lange wie der Heap hoch ist, also \(\O(\log n)\).

Aufgabe (C++ Vorlage hier)

Eure erste Aufgabe ist es nun einen solchen Max-Heap mit den Operationen Insert und ExtractMax zu implementieren.

Suchbäume

Was ist ein Suchbaum?

Ein Suchbaum ist ein Baum mit den Schlüsseln in den Knoten, der folgende Bedingung erfüllt: Die Schlüssel im linken Teilbaum sind immer kleiner als die Wurzel und die Schlüssel im rechten Teilbaum sind immer grösser als die Wurzel. Diese Bedingung soll für jeden Teilbaum gelten.

So einen Baum kann für die Suche sehr gut verwendet werden: Wir beginnen bei der Wurzel und vergleichen den dort gespeicherten Schlüssel mit dem gesuchten Schlüssel. Dann wissen wir, ob wir nach rechts oder nach links gehen müssen (oder den Schlüssel bereits gefunden haben). Dasselbe machen wir dann für den entsprechenden Teilbaum, bis wir an ein Blatt gelangen oder den Schlüssel gefunden haben. Sind wir an einem Blatt angekommen, ohne den Schlüssel gefunden zu haben, so können wir sicher sein, dass der Schlüssel nicht im Baum gespeichert ist.

Wenn wir uns an den Heap erinnern, sehen wir, dass dieser Baum eine strengere Bedingung erfüllt. Dadurch können wir in so einem binären Suchbaum suchen, während das in einem Heap nicht so einfach und schnell möglich ist.

Suchbaum testen durch Traversierung

Wir können die Gültigkeit eines Suchbaumes \(T\) überprüfen indem wir ihn rekursiv durchlaufen, eine sogenannte Traversierung durchführen. Wenn wir dabei alles links vor und alles rechts nach der Wurzel ausgeben, so sollten wir die sortierte Folge der Schlüssel erhalten. Andernfalls wissen wir, dass der Suchbaum nicht die gewünschte Eigenschaft hat. Dies nennt man

Inorder-Traversierung (deutsch: Symmetrische Reihenfolge).

spucke T aus:
    falls T nicht leer
        spucke T.links aus
        zeige Schlüssel der Wurzel
        spucke T.rechts aus

Im Beispiel kommt so \(3,11,18,25,27,34,39\) raus.

Statt die Wurzel in der Mitte auszugeben, können wir das auch anders machen. Auch diese beiden Varianten haben spezielle Namen:

Preorder-Traversierung (deutsch: Hauptreihenfolge)

preorder(T)
    - Wurzel
    - preorder(T.links)
    - preorder(T.rechts)

Im Beispiel: \(25,11,3,18,34,27,39\).

Postorder-Traversierung (deutsch: Nebenreihenfolge)

postorder(T)
    - postorder(T.links)
    - postorder(T.rechts)
    - Wurzel

Im Beispiel: \(3,18,11,27,39,34,25\).

Natürliche Suchbäume

Suchen

Suche (ab Knoten p nach Schlüssel k)
    if p null then erfolglos
    else if k < key von p then suche(links von p, k)
    else if k > key von p then suche(rechts von p, k)
    else gefunden

Unser Wunsch an die Laufzeit für diesen Suchbaum war \(\O(\log n)\). Das können wir auch erreichen, wenn wir den Baum statisch aufbauen können, sich die Schlüsselmenge also nicht dynamisch ändert. Wir bauen den Baum balanciert (so wie beim Heap für Heapsort) und erreichen so logarithmische Höhe.

Wir wollen das jetzt dynamisch machen, also auch Einfüge- und Löschoperationen unterstützen. Die natürlichste Art die Einfügeoperation zu unterstützen ist die folgende:

Einfügen

Einfügen(k)
    Suche ab der Wurzel nach k
    Finden wir k im Baum, müssen wir nichts einfügen
    Sonst, landen wir in einem Blatt p
    Ersetze das Blatt durch einen neuen Knoten mit dem Schlüssel k,

Erreichen wir damit logarithmische Laufzeit? Im schlechtesten Fall leider nicht. Wenn wir in einen leeren Baum die Schlüssel \(1,2,\dots,n\) der Reihe noch einfügen, dann degeneriert der Suchbaum zu einer linearen Liste mit linearer Tiefe. Also: Worst Case \(\Theta(n)\).

Ist es wenigstens im Mittel gut? Für zufällige Eingabereihenfolgen kann man argumentieren, dass wir eine mittlere Suchbaumhöhe von \(\Theta(\log n)\) erreichen.

Entfernen

Wie können wir Schlüssel entfernen? Es genügt nicht, den entsprechenden Knoten zu finden und zu löschen, da wir dabei auch alle Schlüssel in seinen Teilbäumen verlieren. Zusätzlich müssen wir vorsichtig sein, dass wir die Suchbaumeigenschaft nicht zerstören.

Wir unterscheiden drei Fälle:

Entfernen(k)
    Suche ab der Wurzel nach k
    Endet mit Knoten p mit key(p) = k
    1. Fall: p hat kein Kind -> Knoten einfach löschen
    2. Fall: p hat ein Kind -> lenke Zeiger vom Vater aufs Kind
    3. Fall: p hat zwei Kinder -> der interessante Fall!

Der spannende Fall ist also, wenn der zu löschende Knoten zwei Kinder hat. Wir können ihn dann nicht einfach löschen, da es danach keine einfache Möglichkeit gibt, die beiden darunterliegenden Teilbäume in der verbleibenden Suchbaum einzubetten. Der Trick ist es nun stattdessen ein anderes Element zu löschen, welches nur höchstens ein Kind hat.

Für dieses andere Element interessieren wir uns nun für den Knoten mit dem grössten Schlüssel im linken Teilbaum von \(p\). Dies ist der nächstkleinere Wert vor \(k\) in der sortierten Folge aller Schlüssel, genannt (symmetrischer) Vorgänger. Das selbe gilt für den kleinsten Schlüssel im rechten Teilbaum, genannt (symmetrischer) Nachfolger.

Warum können wir sicher sein, dass die nächstkleineren und grösseren Schlüssel in der global sortierten Folge wirklich immer im Teilbaum von \(p\) liegen? Die sortierte Reihenfolge entspricht der Inorder-Traversierung des Suchbaumes. Da beide Kinderteilbäume von \(p\) nicht leer sind, stammen also die Schlüssel unmittelbar vor und nach \(k\) in der sortierten Folge aus dem Teilbaum von \(p\).

Was bringen uns diese Vorgänger und Nachfolger? Der Vorgänger und Nachfolger haben je höchstens ein Kind. Denn hätten sie zwei Kinder, so wären sie in der Traversierung nicht direkt vor/nach \(k\). Somit ist das Entfernen dieser Knoten einer der beiden trivialen Fälle.

c++ = Entfernen im dritten Fall bei Knoten k:     Finde den sym. Vorgänger;      > gehe 1 Schritt links,      > gehe solange rechts wir moeglich (so erreicht man den sym. Vorgänger)     Tausche k mit sym. Vorgänger      Knipse sym. Vorgänger ab oder leite von Vater um. (1. oder 2. Fall)

Aufgabe (C++ Vorlage hier)

Eure zweite Aufgabe ist es nun einen natürlichen Suchbaum genau so zu implementieren! (verwende den sym. Vorgänger beim Löschen)

In der Praxis gibt es viele Tricks um den Code zu vereinfachen. Ein cooler Trick ist es statt Blätter mit null Zeigern ins Leere zeigen zu lassen, allozieren wir einen zusätzlichen Knoten auf den alle Blätter zeigen. Bevor wir dann jeweils eine Suche starten, schreiben wir diesen Schlüssel auf diesen zusätzlichen Knoten. Damit wissen wir, dass die Suche immer den Schlüssel finden wird.

Jetzt haben wir also eine Laufzeit von \(\O(\text{Höhe})\) erreicht für alle Operationen, falls unser Baum am Anfang leer war! Wie hoch wird dieser Baum? Worst Case: \(\Theta(n)\) Best Case: \(\Theta(\log n)\)

Im Normalfall funktionieren natürliche Suchbäume ganz gut, aber wie immer hätten wir gerne Worst Case Garantien.

Rotations-Idee

Können wir diese Teilbäume so umgruppieren, dass die Suchbaumeigenschaft erhalten bleibt, aber die Höhen der Teilbäum links und rechts einander angeglichen werden ohne dass wir viel ändern müssen?

Ja, das geht! Mit folgenden Zeigeränderungen:

Wir nehmen den Baum quasi auseinander und setzen ihn mit \(p\) als neuer Wurzel wieder zusammen und achten dabei darauf, dass die drei Teilbäume am richtigen Ort landen. Eine solche Strukturänderung nennt man Rotation, hier konkret eine Rechtsrotation, und wir können sie in wenigen Zeigeränderungen durchführen.

Auf diesem Konzept der Rotationen aufbauend gibt es diverse Suchbaumstrukturen, die ab und zu rotieren und damit ohne viel Zusatzaufwand eine permanent logarithmische Höhe garantieren können. So zum Beispiel der AVL-Baum, wo sich in jedem Knoten die Höhen der beiden Teilbäume links und rechts um höchstens eins unterscheiden, oder die Red-Black-Trees, wo die Balance-Bedingung etwas komplexer ist. Die Details dieser Strukturen sind meist etwas kompliziert und frimelig, aber wichtig zu wissen ist, dass es geht die Balance zu halten, und dass dies genau das ist, was das std::set intern macht.

[1]Nein. Ist die Eingabe zu Beginn absteigend sortiert, so werden alle \(n-1\) Durchläufe benötigt.
[2]Das \(\Theta\) in diesen Analysen beschreibt immer den schlechtesten Fall und dessen asymptotische genaue Wachstumsordnung. Also kann der Algorithmus \(\Theta(n)\) Bewegungen brauchen, auch wenn wir im besten Fall, gar nichts vertauschen.