Suchen

Das Suchen ist eine grundlegende Operation in der Informatik. Viele Probleme in der Informatik können auf Suchaufgaben zurückgeführt werden.

Gemeint ist mit Suchen das Wiederauffinden eines Datensatzes aus einer Menge von früher gespeicherten Datensätzen, oder das Auffinden einer bestimmten Lösung in einem (potentiell großen) Suchraum möglicher Lösungen. Ein paar einleitende Worte zum Suchproblem findet man hier.

Überblick über verschiedene Suchmethoden

Um sich der Vielseitigkeit des Suchproblems bewusst zu werden, ist es sinnvoll, sich einen Überblick über verschiedene Suchmethoden zu verschaffen.

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu Suchverfahren verwiesen.

Allen gemeinsam ist die grundlegende Aufgabe, ein Datenelement mit bestimmten Eigenschaften aus einer großen Menge von Datenelementen zu selektieren. Dies kann, natürlich ohne jeden Anspruch auf Vollständigkeit, nach einer der jetzt diskutierten Methoden geschehen:

• Schlüsselsuche: meint das Suchen von Elementen mit bestimmtem Schlüssel; ein klassisches Beispiel wäre das Suchen in einem Wörterbuch, die Schlüssel entsprechen hier den Wörtern, die Datensätze wären die zu den Wörtern gehörigen Eintragungen.

• Bereichssuche: Im Allgemeinen meint die Bereichssuche in n-Dimensionen die Selektion von Elementen mit Eigenschaften aus einem bestimmten n-dimensionalen Volumen. Im eindimensionalen Fall will man alle Elemente finden, deren Eigenschaft(en) in einem bestimmten Intervall liegen. Die Verallgemeinerung auf n-Dimensionen ist offensichtlich. Ein Beispiel für die Bereichssuche in einer 3D-Kugel wäre ein Handy mit Geolokalisierung, welches alle Restaurants in einem Umkreis von 500m findet. Lineare Ungleichungen werden graphisch durch Hyperebenen repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

• Ähnlichkeitssuche: Finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google (=Ähnlichkeit zwischen Suchbegriffen und Dokumenten) oder das Suchen des nächstengelegenen Restaurants (Ähnlichkeit zwischen eigener Position und Position des Restaurants). Ein wichtiger Spezialfall ist die nächste-nachbar Suche.

• Graphensuche: Hier wäre beispielsweise das Problem optimaler Wege zu nennen (Navigationssuche). Dieser Punkt wird später im Verlauf der Vorlesung noch einmal aufgegriffen werden.

Im jetzt folgenden wird nur noch die Schlüsselsuche betrachtet werden.

Sequentielle Suche

Die sequentielle oder lineare Suche ist die einfachste Methode, einen Datensatz zu durchsuchen. Hierbei wird ein Array beispielsweise sequentiell von vorne nach hinten durchsucht. Ein prinzipieller Vorteil der Methode ist, dass auf der Eigenschaft der Datenelemente, nach denen das Array durchsucht wird, keine Ordnung im Sinne von > oder < definiert zu sein braucht, lediglich die Identität (==) muss feststellbar sein. Der folgende Python-Code zeigt, wie man sequentielle Suche einsetzen kann:

a = ... # array mit den zu durchsuchenden Elementen

foundIndex = sequentialSearch(a, key) 
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

Wir verwenden hier die Konvention, dass der zugehörige Arrayindex zurückgegeben wird, falls ein Element mit dem Schlüssel key gefunden wird (falls es mehrere solche Elemente gibt, wird das erste zurückgegeben). Das Ergebnis -1 signalisiert hingegen, dass kein solches Element gefunden wurde. Die Funktion sequentialSearch kann folgendermaßen implementiert werden:

def sequentialSearch(a, key):
   for i in range(len(a)):
       if a[i] == key:  # bzw. allgemeiner a[i].key == key 
           return i
   return -1

Wir wollen jetzt die Komplexität dieses Algorithmus bestimmen, wobei die Problemgröße durch N = len(a) gegeben ist.

Dabei nimmt man an, dass der Vergleich in der inneren Schleife (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator eine komplizierte Berechnung mit höherer Komplexität ausführen muss). Bei einer erfolglosen Suche wird dieser Vergleich in der for-Schleife N-mal durchgeführt (<math> \mathcal{O}(N)</math>), bei einer erfolgreichen Suche im Mittel (N/2)-mal (ebenfalls <math> \mathcal{O}(N)</math>). Nach der Verschachtelungsregel erhält man also eine gesamte Komplexität von <math> \mathcal{O}(N)</math>.

Der Name lineare Suche rührt von diesem linearen Anwachsen der Komplexität mit der Arraygröße her.

Binäre Suche

Wie wir weiter unten zeigen werden, gestattet es diese Suchmethode, die Gesamtdauer der Suche in großen Datensätzen beträchtlich zu verringern. Die Methode beruht auf dem Divide and Conquer-Prinzip, wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind hier zu finden.

Die Methode ist nur dann anwendbar beziehungsweise effektiv, wenn folgendes gilt:

1. Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
2. Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden, wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, müsste nach jeder Einfügung das Array neu sortiert werden (unter diesen Umständen wäre die Verwendung eines Suchbaumes geschickter).

Im unterschied zur sequenziellen Suche müssen wir jetzt das Array sortieren bevor die Suchfunktion aufgerufen werden kann:

a = [...,...]     # array
a.sort()   # sortiere über Ordnung des Schlüssels
foundIndex = binSearch(a, key, 0, len(a))  # (Array, Schlüssel, von wo bis wo suchen im Array)
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq</math>  foundIndex < len(a) wenn key gefunden (erster Eintrag mit diesem Wert)

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

def binSearch(a, key, start, end):  # start ist 1. Index, end ist letzter Index + 1
   size = end - start   # <math> \mathcal{O}(1)</math>
   if size <= 0:   # Bereich leer?  <math> \mathcal{O}(1)</math>
       return -1   # also nichts gefunden, <math> \mathcal{O}(1)</math>
   center = (start + end)/2   # Integer Division (d.h. Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes) <math> \mathcal{O}(1)</math>
   if a[center] == key:  # <math> \mathcal{O}(1)</math>
       return center  # Schlüssel gefunden, <math> \mathcal{O}(1)</math>
   elif a[center] < key:  <math> \mathcal{O}(1)</math>
       return binSearch(a, key, center + 1, end)  # Rekursion in die rechte Teilliste
   else:
       return binSearch(a, key, start, center)  # Rekursion in die linke Teilliste

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung verursacht (wir diskutieren unten, wann dies nicht zulässig ist). Wir setzen N = len(a).

Im obigen Code ist zu erkennen, dass fast alle Anweisungen des Algorithmus die Komplexität <math>\mathcal{O}(1)</math>. Nach der Sequenzregel hat auch deren Hintereinanderausführung die Komplexität <math>\mathcal{O}(1)</math>. Es bleibt die Komplexität der Rekursion zu berechnen. Die gesamte Komplexität des Algorithmus (jetzt als Funktion f bezeichnet) setzt sich zusammen aus den oben erwähnten <math>\mathcal{O}(1)</math>-Anweisungen sowie der Rekursion auf einem Teilarray der halben Größe

<math>f(N) = \mathcal{O}(1) + f(N/2) = \mathcal{O}(1) + \mathcal{O}(1) + f(N/4) = ... = \underbrace{\mathcal{O}(1) + ... + \mathcal{O}(1) + \underbrace{f(0)}_{\mathcal{O}(1)\, \rightarrow \,\mathrm{size-Abfrage}}}_{n+1 \,\mathrm{Terme}} </math>

Zur Vereinfachung nehmen wir an <math> N = 2^n </math>, so dass gilt

<math> \rightarrow f(N) = \mathcal{O}(1) \cdot \mathcal{O}(n+1) = \mathcal{O}(n) = \mathcal{O}(\lg N) </math>

Für große Datenmengen ist die binäre Suche also weit effizienter als die lineare Suche. Verdoppelt sich beispielsweise die zu durchsuchende Datenmenge, so verdoppelt sich der Aufwand für die sequentielle Suche - bei der binären Suche hingegen benötigt man lediglich eine zusätzliche Vergleichsoperation.

Für kleine Daten (<math> N = 4,\, 5 </math>) ist die sequentielle Suche jedoch schneller als die binäre Suche, da hier die rekursiven Funktionsaufrufe teurer als das Mehr an Vergleichen sind. Ein anderer ungünstiger Fall ist gegeben, wenn nur sehr wenige Suchanfragen erfolgen (weniger als <math>\mathcal{O}(N)</math> viele). Dann wird der Aufwand durch das Sortieren des Arrays dominiert, ist also <math>\mathcal{O}(N \lg N) </math>. Auch dann ist sequentielle Suche vorzuziehen.

Eine relativ einfache Möglichkeit, die binäre Suche zu verbessern, ist die sogenannte Interpolationssuche. Hierbei wird die neue Position für die Suche, also die Mitte des Arrays, durch eine Schätzung ersetzt, die angibt, wo sich der Schlüssel innerhalb des Arrays befinden könnte. Bei der Suche in einem Telefonbuch nach dem Namen Zebra würde man ja auch nicht in der Mitte anfangen. Näheres hierzu im Buch von Sedgewick.

Um sich den Algorithmus der binären Suche klar zu machen, ist es instruktiv, sich die folgende Tabelle genauer anzusehen, die die sukzessive Belegung der Variablen bei verschiedenen Anfragen beschreibt. Die Testfälle wurden nach dem Prinzip des domain partitioning gewählt. Das zugehörige Array hat die Einträge

a = [2, 3, 4, 5, 6]

gesuchter key	start	end	size	center	return (-1 oder index)	Kommentare
4	0	5	5	2	2	gefunden
2	0	5	5	2		linker Randfall
	0	2	2	1
	0	1	1	0	0	gefunden
1	0	5	5	2		links außerhalb
	0	2	2	1
	0	1	1	0
	0	0	0		-1	nichts gefunden
6	0	5	5	2		rechter Randfall
	3	5	2	4	4	gefunden
5	0	5	5	2		typischer Fall
	3	5	2	4
	3	4	1	3	3	gefunden
7	0	5	5	2		rechts außerhalb
	3	5	2	4
	5	5	0		-1	nichts gefunden

Suchbäume

Effiziente Suchalgorithmen kann man elegent mit Hilfe von Binärbäumen realisieren. Eine kurze Einführung in Binärbäume findet man hier. Die Skizze erläutert wichtige Begriffe:

Bäume sind zweidimensional verkettete Strukturen. Sie gehören zu den fundamentalen Datenstrukturen in der Informatik. Da man in Bäumen nicht nur Daten speichern kann, sondern auch relevante Beziehungen der Daten untereinander, festgelegt über eine Ordnung auf der vergleichenden Dateneigenschaft (Schlüssel), eignen sich Bäume also insbesondere, um gesuchte Daten schnell wieder auffinden zu können.

Ein Binärbaum wie oben skizziert besteht aus einer Menge von Knoten, die untereinander durch Kanten verbunden sind. Jeder Knoten hat einen linken und einen rechten Unterbaum, der auch leer sein kann (in Python ließe sich dies mit None implementieren). Führt eine Kante von Knoten A zu Knoten B, so heißt A Vater von B und B Kind von A. Es gibt genau einen Knoten ohne Vater, den man Wurzel nennt. Knoten ohne Kinder heißen Blätter.

Ein Suchbaum hat zusätzlich die Eigenschaft, dass die Schlüssel jedes Knotens sortiert sind:

Suchbaumbedingung

Für jeden Knoten des Binärbaumes gilt: Alle Schlüssel im linken Unterbaum sind kleiner als der Schlüssel des gegebenen Knotens, alle Schlüssel im rechten Unterbaum sind größer. Wir wollen hierbei annehmen, dass jeder Schlüssel pro Datensatz nur einmal vorkommt, da sich sonst die >- oder <-Relation nicht mehr strikt erfüllen ließe.

Um die Verwendung eines Suchbaums zu motivieren, wollen wir von zwei Annahmen ausgehen:

1. Einfügen und Suchen im Baum wechseln sich ab. (Wenn das Suchen erst beginnt, nachdem alle Einfügungen erfolgt sind, wäre ein dynamisches Array mit binärer Suche wesentlich einfacher.)
2. Der Schlüssel, der die Anordnung bestimmt, kennt eine Ordnung (<-Relation oder >-Relation).

Zunächst definieren wir eine Knotenklasse für den Suchbaum:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

Suche in Binärbäumen

Wir nehmen nun an, dass der Baum durch eine Referenz auf den Wurzelknoten root gegeben ist. Dann kann man folgendermassen suchen:

root = ...    # Wurzel des Suchbaums
nodeFound = treeSearch(root, key)   # None, falls nichts gefunden

Hier verwenden wir die Konvention, dass der passende Knoten zurückgegeben wird, falls key gefunden wurde, oder None andernfalls. Die Suchfunktion wird rekursiv implementiert:

def treeSearch(node, key):
    if node is None:
        return None
    elif node.key == key: # gefunden
        return node       # => Knoten zurückgeben
    elif key < node.key:  # gesuchter Schlüssel ist kleiner
        return treeSearch(node.left, key)  # => im linken Unterbaum weitersuchen
    else:                 # andernfalls 
        return treeSearch(node.right, key) # => im rechten Unterbaum weitersuchen

Einfügen in einen Binärbaum

Bevor wir den Einfügealgorithmus implementieren, müssen wir festlegen, was passieren soll, wenn der einzufügende Schlüssel schon vorhanden ist. Mehrere Möglichkeiten bieten sich an:

• Fehler signalisieren (exception auslösen)
• nichts einfügen
• nichts einfügen, aber einen boolean zurückgeben (false wenn nichts eingefügt wurde, true wenn etwas einfügt wurde)
• nochmals einfügen (z.B. kann man die Klasse Node oben durch einen Zähler erweitern, der angibt, wie oft der betreffende Schlüssel bereits eingefügt wurde)

Die ersten 3 Punkte realisieren eine Mengensemantik, der letzte eine Multimenge. Wir entscheiden uns hier für Möglichkeit 2 (nichts einfügen). Das Prinzip des Einfügens besteht darin, im Baum dorthin abzusteigen, wo der Schlüssel sich befinden müsste (wie bei treeSearch), und dann an der betreffenden Stelle einen neuen Blattknoten zu erzeugen. Die Funktion gibt ein Knotenobjekt zurück, damit die Verkettungen im Elternknoten entsprechend angepasst werden können:

def treeInsert(node, key):
    if node is None:      # richtiger Platz gefunden
        return Node(key)  # => neuen Knoten einfügen
    if node.key == key:   # schon vorhanden
        return node       # => nicht tun
    elif key < node.key:     
        node.left = treeInsert(node.left, key) # im linken Teilbaum einfügen
    else:
        node.right = treeInsert(node.right, key) # im rechten Teilbaum einfügen
    return node

Ein Binärbaum wird aufgebaut, indem treeInsert für jeden Schlüssel aufgerufen wird. Wir verwenden hier ganze Zahlen als Schlüssel. Am Anfang ist der Baum leer:

root = None
root = treeInsert(root, 4)
root = treeInsert(root, 2)
root = treeInsert(root, 3)
root = treeInsert(root, 6)

Entfernen aus einem Binärbaum

Wir legen wiederum zuerst fest, was im Fehlerfall passieren soll, d.h. wenn der Schlüssel nicht vorhanden ist:

• Auslösen einer Exception (KeyError)
• nichts löschen
• nichts löschen, aber ein boolean zurückgeben, das dies signalisiert.

Wir entscheiden uns wieder für Möglichkeit 2. Beim Entfernen eines Knotens unterscheiden wir nun 3 Fälle:

1. node, welcher key enthält, ist ein Blatt => kann einfach gelöscht werden
2. node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
3. node hat beide Unterbäume:
   • Suche Vorgänger: <math>\max_{k < key} (k \in keys)</math> => ersetze node durch seinen Vorgänger und entferne Vorgänger. (Dies führt zu einem effizienten Algorithmus, weil der Vorgänger immer zu Fall 1 oder Fall 2 gehört. Wenn er nämlich einen rechten Unterbaum hätte, könnte er nicht der Vorgänger sein.)

Die Funktion, die den Vorgänger sucht, muss den größten Knoten im lnken Unterbaum suchen. Da diese Funktion nur in Fall 3 aufgerufen wird, gibt es den linken Unterbaum immer.

def treePredecessor(node):
    node = node.left
    while node.right is not None:
        node = node.right
    return node

Die oben angegebenen Fälle werden durch folgende Funktion realisiert:

def treeRemove(node, key):
    if node is None:   # key nicht vorhanden
        return node    # => nichts tun
    if key < node.key: 
        node.left = treeRemove(node.left, key)
    elif key > node.key:
        node.right = treeRemove(node.right, key)
    else:              # key gefunden
        if node.left is None and node.right is None:     # Fall 1
            node = None            
        elif node.left is None:     # Fall 2
            node = node.right       # +
        elif node.right is None:    # Fall 2
            node = node.left
        else:                       # Fall 3
            pred = treePredecessor(node)
            node.key = pred.key
            node.left = treeRemove(node.left, pred.key)
    return node

Komplexitätsanalyse

Um die Komplexität der Operationen auf einem Binärbaum zu bestimmen, müssen wir zunächst einige weitere Begriffe einführen:

Pfad

Ein Pfad zwischen zwei Knoten node₁ und node₂) ist eine Folge von Knoten node_k1,...,node_kn, so dass:

• node_k1 == node₁
• node_kn == node₂
• node_ki und node_ki+1 haben eine gemeinsame Kante.

Ein Baum ist definiert als ein Graph, in dem es zwischen beliebigen Knoten stets genau einen Pfad gibt.

Länge eines Pfades

Anzahl der Kanten im Pfad (= Anzahl der Knoten - 1)

Tiefe eines Knotens

Pfadlänge vom Knoten zur Wurzel des Baumes (die Wurzel hat also die Tiefe 0)

Tiefe des Baumes

maximale Tiefe eines Knotens

Allen Baumoperationen ist gemeinsam, dass sie entlang genau eines Pfades im Baum absteigen (welcher Pfad dies ist ergibt sich aus der Ordnung der Schlüssel). Der Abstieg endet, wenn entweder der gesuchte Schlüssel gefunden wird, oder wenn erkannt wird, dass der Schlüssel nicht vorhanden ist (wenn das Kind, wo der Schlüssel sein müsste, den Wert None hat). Während des Abstiegs werden in jedem Knoten nur Anweisungen ausgeführt, die konstante Zeit benötigen. Daraus folgt, dass die Suche im ungünstigsten Fall die Komplexität <math>\mathcal{O}(T)</math> hat, wobei T die Tiefe des Baumes (= längster Pfad, der durchlaufen werden kann) ist.

Ungünstigster Fall für die Baumoperationen

Um den ungünstigsten Fall für die Baumoperationen zu finden, müssen wir offensichtlich herausfinden, wie groß die Tiefe maximal werden kann. Es ist leicht zu erkennen, dass die Tiefe maximiert wird, wenn man sortierte Daten in den Baum einfügt:

• Fügt man [1,2,3,4,5] in dieser Reihenfolge ein, muss man bei treeInsert stets in den rechten Teilbaum absteigen (weil der nächste Schlüssel immer größer als der größte bisherige Schlüssel ist) und dort ein rechtes Kind einfügen. Es ergibt sich folgender Baum:
  

Dieser Baum hat die Tiefe 4. Die Funktion treeSerach verhält sich dann wie sequentielle Suche, man hat also durch die Verwendung des Suchbaums nichts gewonnen.

Allgemein gilt: Alle Operationen eine binären Suchbaums haben im ungünstigsten Fall die Komplexität <math>\mathcal{O}(N)</math>, wo N die Anzahl der Elemente im Baum bezeichnet. Eine offensichtliche Lösung der Problems besteht darin, die Elemente nicht in einer so ungünstigen Reihenfolge einzufügen (siehe Übungsaufgabe). Allerdings ist dies nicht immer möglich. Abhilfe schaffen dann selbst-balancierende Bäume.

Selbst-balancierende Suchbäume

Balance eines Suchbaumes

Um die Komplexität der Suchbaum-Operationen zu minimieren, wollen wir die Höhe des Baumes minimieren. Wir wollen also die Länge des längsten Pfades verkürzen, ohne dass ein anderer Pfad dadurch unnötig lang wird. Mit anderen Worten wollen wir erreichen, dass alle Pfade von der Wurzel zu den Blättern ungefährt die gleiche Länge haben. Diese Idee kann man formal durch den Begriff der Balance eines Suchbaums fassen. Um die Balance zu definieren, betrachten wir None als zusätzlichen Knoten, als sogenannten sentinel (engl. für Wächter). Der sentinel-Knoten wird als rechter oder linker Nachfolger verlinkt, wenn der entsprechende Nachfolger nicht durch einen echten Knoten belegt ist:

Wir definieren nun:

RS-Pfade

Pfad von root → sentinel. In jedem Binärbaum gibt es mehrere RS-Pfade.

Balance eines Baumes

Differenz zwischen der Länge des längsten und kürzesten RS-Pfads:

<math> B = \max_{P\in\{RS\}} |P| - \min_{P\in\{RS\}} |P|</math>

wobei <math>\{RS\}</math> die Menge aller RS-Pfade bezeichnet, und |P| die Länge des Pfades P.

vollständiger Baum

Balance <math>B=0</math>

Daraus folgt, dass alle Knoten (außer den Blättern) 2 Kinder haben müssen.

perfekt balancierter Baum

Balance <math>B \le 1</math>

alternative Definition für perfekt balancierte Bäume: Für jeden Knoten gilt, dass der rechte und linke Unterbaum ebenfalls perfekt balancierte Bäume sind und ihre Höhe sich höchstens um 1 unterscheidet. Leere Unterbäume sind per Definition perfekt balanciert und haben die Höhe Null.

Größe eines Baumes in Abhängigkeit der Balance

Größe des vollständigen Baumes

Aus der Abbildung erkennt man, dass Ebene k stets 2^k Knoten enthält. Hat der Baum die Tiefe d, dann enthält er

N = 2⁰ + 2¹.....+ 2^d = 2^d+1 - 1

Knoten (und damit ebensoviele Datenelemente).

Größe eines perfekt balancierten Baumes

Für eine gegebene Tiefe d kann kein Baum mehr Elemente enthalten als der entsprechende vollständige Baum. Also gilt

<math> N \le</math> 2 ^d+1 - 1

Der schlechteste perfekt balancierte Baum der Tiefe d ist ein vollständiger Baum der Tiefe d - 1, wo an einem einzigen Knoten noch ein weiteres Datenelement angehängt wurde. Dieser Baum enthält

<math>N = (2^{d-1} - 1) + 1 = 2^d</math>

Datenelemente. Folglich gilt für perfekt balancierte Bäume die Ungleichung

<math>2^d \le N \le 2^{d+1} - 1</math>

und demzufolge auch

<math>\log_2(2^d) \le \log_2(N) \le \log_2(2^{d+1} - 1) < \log_2(2^{d+1})</math>

<math>d \le \log_2(N) < d+1</math>

Da die Baumoperationen im ungünstigsten Fall die Komplexität <math>\mathcal{O}(d)</math> haben, gilt für perfekt balanciert Bäume, dass alle Operationen im schlechtesten Fall die Komplexität

<math>\mathcal{O}(\log(N))</math>

haben, das heisst logarithmische Komplexität. Ein perfekt balancierter Baum wird z.B. durch die Datenstruktur des AVL-Baums realisiert. Die Implementation eines AVL-Baums ist jedoch kompliziert. Es zeigt sich ausserdem, dass die Eingenschaft der perfekten Balance gar nicht notwendig ist, um logarithmische Komplexität zu garantieren. Wir definieren:

• Ergibt die Komplexität der Suche im schlechtesten Fall: Anzahl der Vergleiche pro Knoten( = 2 bzw. = 3)<math>\ast</math>Anzahl der Knoten

<math>\Rightarrow ~f(N)\le 2d \le 2\log_{2}{ N} = \mathcal{O}(\log_{2}{N})</math>

• perfekt balancierter Baum => AVL-Baum
• balancierter Baum:

<math>\forall N:d(N)\le c \ast d (N)</math> und <math>1 \le c < \mathcal {1}</math>

d ist die Tiefe von perfekt balancierten Baum

Komplexität der Suche:<math> ~f(N)\le c\ast 2\log_{2}{ N} = \mathcal{O}(\log_{2}{N})</math>

algorithmisch einfacher als perfekt balancierter Baum, aber fast genauso schnell

Minimiere Balance (erzeuge balancierten Baum):

1. Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
2. Selbstbalancierter Baum:
   • Überprüfen der Balance nach jedem Einfügen
   • Umstrukturieren des Baumes, falls Balance > 1 (Suchbaum-Bedingung muss erhalten bleiben)
   • AVL-Bäume (älteste Variante)
   • Rot-Schwarz-Bäume (verbreiteste Variante)
   • Treaps (flexibelste Variante, siehe Übung)
   • Splay trees
   • Andersson Trees (einfachste Variante)

(#* Skip Lists (schnellste Variante, aber kein Binärbaum))

Umstrukturieren, so dass Suchbaumbedingung erhalten bleibt:

Rotation: elementare Umstrukturierungen

def rotateRight(node):
    newRoot = node.left
    node.left = newRoot.right
    newRoot.right = node
    return newRoot

def rotateLeft(node):
    newRoot = node.right
    node.right = newRoot.left
    newRoot.left = node
    return newRoot

 def insertTree(node,key):
   if node is sentinel:       #(None = sentinel)
       return Node(key)       
   if node.key == key:
       return Node
   if key < node.key:
       Node = insertTree(node.left, key)
   else:
       node.right = insertTree(node.right, key)
  #optimiere Balance:
       return node

Anderson-Bäume

 class Node:
   def__init__(self, key):
       self.key = key
       self.left = selft.right = None
       #einfügen:
       self.level = 1

level : kodiert Abstand von sentinel

Regeln

Es gibt vertikale Kanten(parent.level == child.level + 1 ) und horizontale Kanten(parent.level == child.level)

• verfeinerter Regel : level kodiert reduzierten Abstand von Setinel (d.b. horizontale Kanten werden nicht gezählt)

(die nächste zwei Regeln sichern die Balance):

• alle RS-Pfade haben die gleiche reduzierte Länge oder root hat bei allen Pfaden das gleiche Level
• kein Pfad hat 2 aufeinanderer folgende horizontale Kanten

• nur Kanten zum rechten Kind dürfen horizontal sein
• die reduzierte Höhe jedes Blatts ist hr=1

Beweis

Vereinfachung des Algorithmus

Satz:ein Anderson-Baum ist balanciert.

• 1. Sei hr- die reduzierte Höhe

<math>\Rightarrow</math> jeder Teilbaum enthält mindestens <math>N\ge 2^{hr} -1 </math> Knoten

a). Blätter : reduzierte Höhe 1 => <math> N\ge 2^{1} - 1 = 1</math>

b). inneren Knoten: jeder Unterbaum hat mindestens reduzierte Höhe <math> ~hr - 1 </math>

<math>\Rightarrow</math> jeder Unterbaum hat mindestens <math> ~2^{hr} -1 </math> Knoten

<math>\Rightarrow</math> <math>N \ge 2 (2^{hr-1} -1)+1 = 2^w - 2 + 1 = 2^{hr} -1</math>

alle RS-Pfade heben gleiche Länge

• 2. Kein Pfad hat 2 aufeinanderfolgende horizontal Kanten

<math>\Rightarrow d \le 2 hr + 1</math>

• 3. zusammen:

<math>N \ge 2^{\frac {d}{2}} - 1 </math>

<math>log_{2}{ N}+1\ge log 2^{\frac {d}{2}} - 1 \ge \frac {d}{2}</math>

<math> ~d < 2 log_{2}{(N + 1)}</math> - balancierter Baum

Suchzeit : <math> ~ f(N) = \mathcal{O}(log{N})</math>

Wie erreicht man die Balance

Rotation

  def rotateRight (node):
     root = node.left
     node.left = root.right
     root.right = node
     return root
  def rotateLeft(node):
     root = node.right
     node.right = root.left
     root.left = node
     return root

Optimierung der Balance

      if node.left is not sentinel and node.level==node.left.level:
           node > rotateRight(node)
      if node.right is not sentinel and node.right.right is  not sentinel and node.level==rotate.right.right.level:
           node = rotateLeft(node)
           node.level += 1

---

Beziehungen zwischen dem Suchproblem und dem Sortierproblem

Sortieren mit Hilfe eines selbst-balancierenden Suchbaums

Daraus resultiert der folgende Suchalgorithmus:

def treeSort(node,array):     # dynamisches Array als 2. Argument
    if node is None:     # <math>\mathcal{O}(1)</math>
        return None:
    treeSort(node.left, array)     # rekursiv
    array.append(node.key)     # <math>\mathcal{O}(1)</math>
    treeSort(node.right, array)     # rekursiv

Komplexität:

<math>
f(N)=\mathcal{O}(1)+f(N_\mathrm{left})+f(N_\mathrm{right})=\mathcal{O}(1)+\mathcal{O}(1)+f(N_\mathrm{leftleft})+f(N_\mathrm{leftright})+\mathcal{O}(1)+f(N_\mathrm{rightleft})
+f(N_\mathrm{leftright})=N\ast\mathcal{O}(1)=\mathcal{O}(N)
</math>

Sortier-Pseudocode:

Sortieren:
    (Array) a     # unsortiert
    (tree) t     # zunächst leer
(dynamisches Array) r     # später sortiert
for e in a:
    t = treeInsert(t, e)
treeSort(t, r)

Sortieren als Suchproblem

Systematisches Fragen mit True und False kann auch als Baum dargestellt werden.

Hier ein Beispiel.Als Eingabe sind drei Zahlen angegeben a={1,2,3},wobei die Reihenfolge nicht bekannt ist.

Also mit Eingabe von drei Elemnten müssen im ungünstigsten Fall drei Schritte vorgenommen werden.
Die allgemeine Regel lautet: es gibt N mögliche Lösungen
=>der Baum muss N Blätter haben
=>ein baum mit N Blättern hat mindestens die Höhe logN

vollständiger Baum (oder balancierter Baum)[1]
2^d+1 Knoten
2^d Blätter

Sortieren

N = n!wenn das Arrey n Elemente hat
Zum Beispiel: 3! = 1*2*3 = 6
log6 <math>\approx</math> 2,6 => d = 3 - bei dem Frage-Baum brauch man im ungünstigsten Fall drei Schritte (True/False)
log6 <math>\approx</math> 2,6 - weil nicht jeder Pfad zu Ende durchgelaufen sein soll, um die Lösung zu bekommen.
d<math>\ge</math>log<math>_2</math>n! = log<math>_2</math>(1,2...n) = log<math>_2</math>1 + log<math>_2</math>2 + ... + log<math>_2</math>n = <math>\sum_{n=1}^n log_2n </math>

Abschätzung von Summen durch Integrale

gegeben : f(x) - monoton wachsend

<math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lfloor x \big\rfloor)dx</math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(x)dx </math> <math>\le</math> <math>\textstyle \int\limits_{x_1}^{x_2} f(\big\lceil x \big\rceil)dx</math>

<math>\downarrow</math>

<math>\textstyle \int\limits_{x_1}^{x_1 + 1} \underline{f(x_1)}dx</math> + ...+ <math>\textstyle \int\limits_{x_2-1}^{x_2} f(x_2 - 1)dx </math> = <math>\sum_{k=x_1}^{x_2-1} f(k)</math>
( angenommen <math>x_1</math> und <math>x_2</math> <math>\in </math> <math>\mathbb{N},\mathbb{Z}</math> )

wobei f(<math>x_1</math>) = f(<math>\big\lfloor x \big\rfloor </math><math>)_{x_1}^{x_1 +1}</math>

<math>\textstyle \int\limits_{x_1}^{x_1 +1} f(x_1)dx</math> = f(<math>x_1</math>) <math>\textstyle \int\limits_{x_1}^{x_1 + 1} 1dx</math> = f(<math>x_1</math>)x<math>\textstyle \int\limits_{x_1}^{x_1 + 1}</math> = f(x_1)

<math>\sum_{k=x_1}^{x_2-1} f(k) \le \textstyle \int\limits_{x_1}^{x_2} f(x)dx</math>

<math>\sum_{k=x_1 +1}^{x_2} f(k) \ge \textstyle \int\limits_{x_1}^{x_2} f(x)dx \iff</math> <math>\sum_{k=x_1}^{x_2} f(x) \ge \textstyle \int\limits_{x_1 - 1}^{x_2} f(x)dx </math>

für uns gilt: f(x) = log<math>_2</math>(x)

log<math>_2</math>1 + <math>\sum_{k=2}^{n} log_2 x\ge\textstyle \int\limits_{1}^{n} log_2 (x)dx </math> = <math>\frac{1}{ln2}\textstyle \int\limits_{1}^{n} log(x)dx</math> = <math>\frac{1}{ln2}</math> [xlogx - x]<math>_{x = 1}^n</math> = nlog<math>_2</math>(n) - <math>\frac{n - 1}{ln2}</math> = <math>\Omega</math>(nlog<math>_2</math>n)

<math>\Rightarrow</math> d = log<math>_2</math>n! = <math>\Omega</math>(nlogn)

kein Sortieralgorithmus auf Basis paarweise Vergleiche ist asymthotisch schneller als Mergesort