Alda - User contributions [en]

Suchen

2008-05-22T14:04:54Z

Tgoeckel: /* Umstrukturieren, so dass Suchbaumbedingung erhalten bleibt: */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[[Image:Baum_Pfad.png]]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets genau einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [[Image:Balance.png]]
*: Tiefe T = 4, Balance = 4
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# 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

[[Image:Baum_Rotation.png]]

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

File:Baum Rotation.png

2008-05-22T14:04:08Z

Tgoeckel:

Suchen

2008-05-22T13:41:51Z

Tgoeckel: /* Komplexitätsanalyse */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[[Image:Baum_Pfad.png]]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets genau einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [[Image:Balance.png]]
*: Tiefe T = 4, Balance = 4
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# 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

[Graph]

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

File:Baum Pfad.png

2008-05-22T13:40:51Z

Tgoeckel:

Suchen

2008-05-22T13:30:11Z

Tgoeckel: /* Ungünstigster Fall von treeSearch */

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[Graph]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets geneu einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [[Image:Balance.png]]
*: Tiefe T = 4, Balance = 4
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# 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

[Graph]

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

File:Balance.png

2008-05-22T13:27:56Z

Tgoeckel:

Suchen

2008-05-22T13:27:25Z

Tgoeckel:

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-) 
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[Graph]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets geneu einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]:
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# 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

[Graph]

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

Suchen

2008-05-22T12:12:16Z

Tgoeckel:

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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]

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"
! gesuchter key !! start !! end !! size !! center !! return (-1 oder index) !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

== Komplexitätsanalyse ==

* Pfad (Zwischen node1 und node2):
**Folge von Knoten (nodek1,...,nodekn), sodass:
*** nodek1 == node1
*** nodekn == node2
*** nodeki und nodeki+1 haben eine gemeinsame Kante.
[Graph]
(Ein Baum ist ein Graph, indem es zwischen beliebigen Knoten stets geneu einen Pfad gibt.)

* Länge eines Pfades: Anzahl der Kanten = Anzahl der Knoten - 1
* Tiefe eines Knotens: Pfadlänge vom Knoten zur Wurzel des Baumes.
* Tiefe des Baumes: maximale Tiefe eines Knotens
* Balance eines Baumes: maximale Tiefe(k) - minimale Tiefe(k) (k <math>\in</math> Blätter)

== Ungünstigster Fall von treeSearch ==

Komplexität von treeSearch = Länge des Pfades zum Knoten wo <tt>key</tt> gefunden wird, oder erkannt wird, dass <tt>key</tt> nicht im Baum ist. 
=> Ungünstigster Fall: <tt>key</tt> wird nicht gefunden, aber für diese Entscheidung muss der Längste Pfad vollständig durchlaufen werden. 
=> Ungünstigster Fall: <math>\mathcal{O}(T)</math> wo T = Tiefe des Baumes
*: [1,2,3,4,5]: [Graph]
=> Ungünstigster Fall: <math>\mathcal{O}(N)</math> wo N = Anzahl der Elemente.

== Aufgabe ==

Minimiere Balance (erzeuge balancierten Baum):
# Einfügen in geschickter Reihenfolge (siehe Übungsaufgabe)
# 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

[Graph]

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

Suchen

2008-05-21T09:37:41Z

Tgoeckel:

Es wäre super wenn jemand ganz kurz schreiben könnte, was am Donnerstag zu den Funktionen treeInsert/Remove/HasKey gemacht wurde, was man ja für den aktuellen Übungszettel braucht. Danke :-)
/edit: an eine Funktion "HasKey" kann ich mich aus der Vorlesung nicht erinnern. Wenn die jemand hat, bitte eintragen. - Protokollant


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 einer oder mehrerer Datensätze aus einer Menge von früher gespeicherten Datensätzen. Ein paar einleitende Worte zum Suchproblem findet man [http://de.wikipedia.org/wiki/Suche hier].

== Überblick verschiedener Suchmethoden ==

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

Hier sei auch auf einen bereits existierenden Wikipedia-Artikel zu [http://de.wikipedia.org/wiki/Suchverfahren 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 [http://de.wikipedia.org/wiki/Hyperebene 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 wichtigster 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 einfachst mögliche 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 (Pseudo)-Python-Code zeigt eine Implementation der Suchmethode.

a = ... # array

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

def SeqSearch(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 <tt>N = len(a)</tt> gegeben ist.

Dabei nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist (diese Annahme könnte verletzt sein, wenn der Vergleichsoperator überladen ist und dadurch eine höhere Komplexität hat). Dieser Vergleich wird in der for-Schleife jeweils N-mal durchgeführt (<math> \mathcal{O}(N)</math>), so dass man nach der Verschachtelungsregel eine gesamte Komplexität von <math> \mathcal{O}(N)</math> erhält.

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 [http://de.wikipedia.org/wiki/Divide_and_Conquer 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 [http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche hier] zu finden.

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

# Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
# 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, so ist unter Umständen die Implementierung über einen [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum Binärbaum] (siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode (wir setzen wieder <tt>N = len(a)</tt>):

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)

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 # <math> \mathcal{O}(1)</math>
center = (start + end)/2 # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes <math> \mathcal{O}(1)</math>
if a[center] == key: # <math> \mathcal{O}(1)</math>
return center # <math> \mathcal{O}(1)</math>
elif a[center] < key: <math> \mathcal{O}(1)</math>
return binSearch(a, key, center + 1, end) # Rekursion
else:
return binSearch(a, key, start + 1, center) # Rekursion

Zur Berechnung der Komplexität dieses Algorithmus vernachlässigen wir zunächst den Aufwand, den die Sortierung weiter oben verursacht. Dieser Schritt mag oder mag nicht zulässig sein.

Nach der Sequenzregel haben auch alle <math>\mathcal{O}(1)</math> Anweisungen 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 und ist

<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>

Falls jetzt gilt <math> N = 2^n </math>

<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. Das Array hat die Einträge

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

{| class="wikitable" style="text-align:center" border="1" cellpadding="5" cellspacing="0"

! key !! start !! end !! size !! center !! return !! Kommentare
|- bgcolor="#e0e0e0"
| 4 ||0 || 5 || 5 || 2 || 2 || gefunden
|-
| 2 || 0 || 5 || 5 || 2 || || linker Randfall
|-
| ||0 || 2 || 2 || 1 || ||
|-
| || 0 || 1 || 1 || 0 || 0 || gefunden
|- bgcolor="#e0e0e0"
| 1 ||0 || 5 || 5 || 2 || || links außerhalb
|- bgcolor="#e0e0e0"
| ||0 || 2 || 2 || 1 || ||
|- bgcolor="#e0e0e0"
| ||0 || 1 || 1 || 0 || ||
|- bgcolor="#e0e0e0"
| ||0 || 0 || 0 || || -1 || nichts gefunden
|-
| 6 ||0 || 5 || 5 || 2 || || rechter Randfall
|-
| || 3 || 5 || 2 || 4 || 4 || gefunden
|- bgcolor="#e0e0e0"
| 5 ||0 || 5 || 5 || 2 || || typischer Fall
|- bgcolor="#e0e0e0"
| ||3 || 5 || 2 || 4 || ||
|- bgcolor="#e0e0e0"
| || 3 || 4 || 1 || 3 || 3 || gefunden
|-
| 7 ||0 || 5 || 5 || 2 || || rechts außerhalb
|-
| || 3 || 5 || 2 || 4 || ||
|-
| ||5 || 5 || 0 || || -1 || nichts gefunden
|}

== Suche in einem Binärbaum ==

Eine kurze Einführung in Binärbäume findet man [http://de.wikipedia.org/wiki/Bin%C3%A4rbaum hier].

[[Image:Baum.png|text-top|300x300px|Zur Illustration von Bäumen]]

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. Alle Schlüssel im linken Unterbaum sind kleiner, alle Schlüssel im rechten Unterbaum sind größer als ihr Vater. 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 in einem Baum suchen zu können, wollen wir von zwei Annahmen ausgehen:
# 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 wie oben wesentlich einfacher.)
# Der Schlüssel, der die Anordnung bestimmt, kennt eine [http://de.wikipedia.org/wiki/Ordnungsrelation Ordnung] (<-Relation oder >-Relation).

Der folgende Python-Code zeigt beispielhaft, wie man in einem Suchbaum suchen könnte. Der Konstruktor für einen Knoten des Suchbaums ließe sich zum Beispiel so implementieren:

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

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

def treeSearch(node, key):
if node is None:
return None
elif node.key == key:
return node
elif key < node.key:
return treeSearch(node.left, key)
else:
return treeSearch(node.right, key)

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)

== Insert ==

Was passiert wenn der key (Schlüssel) schon vorhanden ist?
* error (exception)
* nichts einfügen
* nichts einfügen aber einen boolean return zurückgeben (einfügen=true, false)
* nochmals eingefügt (z.B. in der Node Klasse)

Wobei die ersten 3 Punkte zur Mengensemantik gehören und der letzte eine Multimenge ist.

Algorithmus im zweiten Fall (nichts einfügen):

def treeInsert(node, key):
if node is None
return Node(key) # Alternative Schreibweise: node = Node(key)
if node.key == key: # und dann:
return node # pass
elif key < node.key: # links im Baum
node.left = treeInsert(node.left, key)
else:
node.right = treeInsert(node.right, key)
return node

== Remove ==
Fälle:
# key (bzw. Knoten der key enthält) ist ein Blatt => einfach löschen
# node hat nur linken Unterbaum oder nur rechten Unterbaum => durch Unterbaum ersetzen
# node hat beide Unterbäume:
#* Suche Vorgänger: max k < key (k <math>\in</math> keys); Vorgänger ist immer ein Fall 1 oder Fall 2
#*:=> ersetze node durch Vorgänger und entferne Vorgänger

def treePredecessor(node): # wird nur bei Fall 3 aufgerufen
node = node.left
while node.right is not None:
node = node.right
return node

def treeRemove(node, key):
if node is None:
return node
if key < node.key:
node.left = treeRemove(node.left, key)
elif key > node.key:
node.right = treeRemove(node.right, key)
else:
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:
pred = treePredecessor(node)
node.key = pred.key
node.left = treeRemove(node.left, pred.key)
return node

[Rest folgt]

Sortieren

2008-05-12T14:42:02Z

Tgoeckel: /* Charakterisierung der Effizienz von Algorithmen */

----
== Laufzeitmesung in Python ==

Verwendung der '''timeit-Bibliothek''' für die Hausaufgabe.

* Importiere das timeit-Modul: <tt>import timeit</tt>
* Teile den Algorithmus in die Initialisierungen und den Teil, dessen Geschwindigkeit gemessen werden soll. Beide Teile werden in jeweils einen (mehrzeiligen) String eingeschlossen:

+--------+ +----+ setup = """ prog = """
| algo | --> |init| +----+ +----+
| | +----+ |init| |prog|
| | +----+ +----+
| | +----+ """ """
| | --> |prog|
+--------+ +----+

* aus den beiden Strings wird ein Timeit-Objekt erzeugt: <tt>t = timeit.Timer(prog, setup)</tt>
* Frage: Wie oft soll die Algorithmik wiederholt werden
:z.B. N = 1000
* Zeit in Sekunden für N Durchläufe: <tt>K = t.timeit(N)</tt>
:Zeit für 1 Durchlauf: K/N

----
3.Stunde am 16.04.2008

==Sortierverfahren==

=== Motivation ===
'''Def:'''
Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren.

'''Anwendungen'''
* Sortierte Daten sind häufig Vorbedingungen für Suchverfahren (Speziell für Algorithmen mit Log(N) Komplexität)
* Darstellung von Daten gemäß menschlicher Wahrnehmung
* Bemerkung: aus programmiertechnischer Anwenwendungssicht hat das Sortierproblem an Relevanz verloren da
** Festplatten / Hauptspeicher heute weniger limitierenden Charakter haben, so dass komplizierte, speicher-sparende Sortieralgorithmen nur noch in wenigen Fällen benötigt werden.
** gängige Programmiersprachen heute typenabhängige Algorithmen zur Verfügung stellen. Der Programmierer braucht deshalb sich in den meisten Fällen nicht mehr um die Implementierung von Sortieralgorithmen kümmern. In C/C++ sorgen dafür beispielsweise Methoden aus der [http://de.wikipedia.org/wiki/Standard_Template_Library STL]

=== Vorraussetzungen/ Spielregeln ===
==== Mengentheoretische Anforderungen====
;Definition Totale Ordnung/ Total gordnete Menge:
Eine Totale Ordnung / Total geordnete Menge ist eine binäre Relation
<math>R \subseteq M \times M</math> über einer Menge <math>M</math>, die transitiv, antisymmetrisch und total ist. 

<math>R</math> sei dargestellt als infix Notation <math>\le </math> dann, falls M total geordnet, gilt
<math> \forall a,b,c \ \epsilon M </math> 
(1) <math>a \le b \bigwedge b \le a \Rightarrow a=b </math> (antisymmetrisch) 
(2) <math>a \le b \bigwedge b \le c \Rightarrow a \le c </math> (transitiv) 
(3) <math>a \le b \bigvee b \le a </math> (total) 
Bemerkung: aus (3) folgt <math> a \le a </math> (reflexiv) 

''Hab in der Wiki eine gute Seite dazu gefunden [http://de.wikipedia.org/wiki/Ordnungsrelation'' Ordnungsrelation]

==== Datenspeicherung ====
a) Array (Grafik folgt noch)

b) Vekettete Liste
Nachteil Adressierung bsp: 10 > 9

==== Charakterisierung der Effizienz von Algorithmen ====

:(a) Komplexität O(1), O(n), etc. wird in Kapitel [[Effizienz]] erklärt.
:(b) Zählen der notwendigen Vergleiche
:(c) Messen der Laufzeit mit 'timeit' (auf identischen Daten)

'''Rekursive Zerlegung'''
zerlegt Ursprüngliche Probleme in kleinere Probleme und wendet sie auf die kleineren Probleme an;
daraufhin werden die Teilprobleme zur Lösung des Gesamtproblems verwendet.
'''Aufwand'''
für N Eingaben, hängt ab vom Aufwand der Eingaben geringeren Umfangs ab. (Teilprobleme)

----
----
4. Stunde, am 17.04.2008
 
(Fortsetzung der Stunde vom 16.04.2008)
 

=== Mergesort ===
==== Algorithmus ====
# <tt>c ← merge(a,b)</tt> (Siehe Mitschrift der Stunde am 16.04.2008)
# '''rekursiver Mergesort''':

mergesort(m) ← { #m ist ein Array
if |m| > 1 #True, wenn m mehr als 1 Element hat.
a ← mergesort(m[1:<|m|/2])
b ← mergesort(m[|m|/2-1:|m|])
c ← merge(a,b)
return(c)
else
return(m)
}

Bei der Sortierung mit Mergesort wird das Array immer in zwei Teile geteilt. → Es

entsteht ein Binärbaum der Tiefe <math>lgN</math>.

[[Bild fehlt noch]]

Zeitkomplexität: <math>C(N) - N \cdot lgN</math>

==== Komplexität ====
Komplexität: <math>C(N) = 2 \cdot \left( \frac{N}{2} \right) + N = N \cdot log_2 N

\cdot N</math> (für N = <math>2^n</math> )

Erklärungen zur Formel:
* <math> C \left(\frac{N}{2}\right) </math>: für jede Hälfte des Arrays
* <math> + N </math>: für das Zusammenführen

==== weitere Eigenschaften von MergeSort ====
* Mergesort ist '''stabil''', weil die Position gleicher Schlüssel im Algorithmus

<tt>merge(a,b)</tt> nicht verändert wird - wegen <tt>„<”</tt> hat das linke

Element Vorrang.
* Mergesort ist '''unempfindlich gegenüber der Reihenfolge der Eingabedaten'''.

Grund dafür ist die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge

1.
* Diese Eigenschaft ist dann unerwünscht, wenn ein Teil des Arrays oder gar das

ganze Array schon sortiert ist. Es wird nämlich in jedem Fall das ganze Array neu

sortiert.

=== Quicksort ===

* Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [http://de.wikipedia.org/wiki/C._A._R._Hoare] entwickelt. Es gibt viele Implementierungen von Quicksort, siehe vgl. [http://de.wikipedia.org/wiki/Quicksort].
* Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.

==== grundlegender Algorithmus ====

quicksort(l,r) ← { #l: linke Grenze, r: rechte Grenze des Arrays
#Das Array läuft also von l bis r (a[l:r])
if r > l
i ← partition(l,r) #i ist das Pivot-Element
quicksort(l,i-1) #quicksort auf beide Hälfte des Arrays anwenden
quicksort(i+1,r)
}
Dieser Algorithmus wird rekursiv für zwei Teilstücke links und rechts des Pivot-Elements aufgerufen. Das Pivot-Element ist nach diesem Schritt an der richtigen Position (d.h. links von der Stelle i stehen nur kleinere, rechts von i nur größere Elemente als das Pivot-Element).
Die Methode partition sorgt dafür, dass diese Bedingung erfüllt ist.

==== Algorithmus für <tt>partition</tt> ====
Aufgabe: Ordne <tt>a</tt> so um, dass nach der Wahl von <tt>i</tt> (Pivot-Element)

gilt:
# <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
# <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right]

\right\} : x \leq a \left[ i \right]</math>
# <math>\forall x \in \left\{ a \left[ i+1 \right], ... a \left[ r \right]

\right\} : x \geq a \left[ i \right]</math>

[[Abbildung fehlt noch]] a[i] heißt Pivot-Element (p)

i ← partition(l,r) ← {
p ← a[r] #p: Pivot-Element. Hier wird willkürlich das rechteste Element
# als Pivot-Element genommen.
i ← l-1 #i und j sind Laufvariablen
j ← r

repeat
repeat
i ← i+1 #Finde von links den ersten Eintrag >= p
until a[i] >= p

repeat
j ← j+1 #Finde von rechts den ersten Eintrag <= p
until a[j] <= p
swap(a[i], a[j])
until j <= i #Nachteile: p steht noch rechts
swap(a[i], a[j]) #Letzter Austausch zwischen i und j muss
#zurückgenommen werden
swap(a[i], a[r])
return(i)
}

[[Abbildung fehlt noch]]

[[Beispiel fehlt noch]]

Bemerkungen zur gegebenen Implementierung:
# Sie benötigt ein Dummy-Minimalelement.
#* Dieses Element ist durch zusätzliche <tt>if</tt>-Abfrage vermeidbar, aber die

<tt>if</tt>-Abfrage erhöht die Komplexität des Algorithmus (schlechte Performanz).
# Sie ist ineffizient für (weitgehend) sortierte Arrays, da sich folgende

Aufteilung für die Partitionen ergibt:
# Erste Partition: <tt>[l,i-1]</tt>, zweite Partition: <tt>[i+1,r]</tt>
# Die erste Partition umfasst <tt>N-1</tt> Elemente
# Die zweite Partition ist leer (bzw. sie existiert nicht), weil das Pivot-Element <tt>p = r</tt> gewählt wurde. Das Array wird also elementweise abgearbeitet.
# → <tt>N</tt> einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx

\frac{N^2}{2}</math> (siehe Berechnung vom 16.04.2008)
# Für identische Schlüssel sollten beide Laufvariablen stehen bleiben.
# Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
# Für identische Schlüssel können die Abbruchbedingungen verbessert werden (siehe

Sedgewick).

==== Komplexität ====

<math>C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k)

\right]</math> für <math> N>1;\, C_1 = C_0 =0 </math>

Anmerkungen zur Formel:
# <math>(N+1)</math>: Vergleiche für jeden Aufruf
# <math>k</math>: Teilungspunkt
 
<math>
\frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N}

\sum_{k=1}^{N} C(k-1)
</math>
 

<math>
C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right]
\overset{\cdot N}{\longleftrightarrow} </math>
 

<math>
N \cdot C(N) = N \left[ (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) \right]
\overset{-\, (N-1) \cdot C(N-1)}{\longleftrightarrow} </math>
 

<math>
N \cdot C(N) - (N-1) \cdot C(N-1) = N(N+1) - (N-1) \cdot N + 2 \sum_{k=1}^{N}

C(k-1) - 2 \sum_{k=1}^{N} C(k-1) </math>
 

<math>
= N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) \longleftrightarrow </math>
 

<math>
N \cdot C(N) = N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) + (N-1) + (N-1) \cdot

C(N-1) = 2N + (N+1) \cdot C(N-1) \overset{/N(N+1)}{\longleftrightarrow} </math>
 

<math>
\frac{C(N)}{N+1} = \frac{C(N-1)}{N} + \frac{2}{N+1} </math>
 

<math>
= \frac{C(N-2)}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
 

<math>
= \frac{C(N-3)}{N-2} + \frac{2}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
 

<math>
= ... = </math>
 

<math>
= \frac{C(2)}{3} + 2 \sum_{k=3}^{N} \frac{1}{k+1} \approx 2 \sum_{k=3}^{N}

\frac{1}{k+1} \approx 2 \int_1^N \frac{1}{k} dk = 2 \cdot ln N
</math>
 
Für sehr große N gilt:
<math>\approx 2 \sum_{k=1}^{N} \frac{1}{k}</math> beziehungsweise <math> \geq 2

\sum_{k=1}^{N} \frac{1}{k}</math>
 
Mittlere Komplexität:
<math>C(N) = 2(N+1) \cdot lnN \approx 2N \cdot lnN </math>
 
==== Verbesserungen des Algorithmus ====
# Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks.
# "r" wird immer kleiner → Der rekursive Aufruf lohnt sich nicht mehr. → Explizites Sortieren einsetzen.
# Das Pivot-Element könnte geschickter gewählt werden: Median.
 
[[Special:Contributions/147.142.207.188|147.142.207.188]] 19:31, 23 April 2008 (UTC)