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: