Suchen

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

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 auch hier.

Überblick verschiedener Suchmethoden

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

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 durch graphisch durch Hyperebenen repräsentiert. In 2D sind diese Hyperebenen Geraden. Die Ungleichungen können dann den Lösungsraum in irgendeiner Form begrenzen.

• Ähnlichkeitssuche: finde Elemente, die gegebenen Eigenschaften möglichst ähnlich sind. Ein prominentes Beispiel ist Google oder das Suchen des nächsten Restaurants.

• 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
len(a) == N
foundIndex = seqSearch(a, key) 
# foundIndex == -1 wenn nichts gefunden, 0 <math>\leq </math> foundIndex <math> \leq </math> N 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.

Nimmt man an, dass der innerste Vergleich (a[i] == key) jeweils <math> \mathcal{O}(1)</math> ist - was dann sinnvoll ist, wenn der Vergleichsoperator nicht überladen und somit evtl. komplexer ist. 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 Divide and Conquer-Prinzip, wobei die Suche in jedem Schritt rekursiv auf eine Hälfte des Datensatzes eingeschränkt wird. Weitere Details zur Methode sind hier zu finden.

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

1. Auf der Eigenschaft der Daten, die zur Suche verwendet wird, ist eine Ordnung im Sinne von < oder > definiert.
2. Wir wollen uns auf Datensätze beschränken, die schon fertig aufgebaut sind, in die also keine neuen Elemente mehr eingefügt werden wenn man mit dem Suchen beginnt. Ist dies nicht der Fall, so ist unter Umständen die Implementierung über einen Binärbaum

(siehe auch weiter unten) geschickter.

Der folgende Algorithmus zeigt eine beispielhafte Implementierung der Methode:

a = []   # array
len(a) == N
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)

def binSearch(a, key, start, end):  # start ist 1. Index, end ist letzter Index + 1
   size = end - start 
   if size <= 0:   # Bereich leer?
       return -1
   center = (start + end)/2   # Integer Division, Ergebnis wird abgerundet, wichtig für ganzzahlige Indizes
   if a[center] == key:
       return center
   elif a[center] < key:
       return binSearch(a, key,center + 1, end)
   else:
       return binSearch(a, key, start, center)