Elementare Suchmethoden

Beschreibung / Inhalt
Das Dokument beschreibt verschiedene Methoden zur Suche nach gespeicherten Informationen. Es beginnt mit einer Einführung und erklärt dann die sequentielle Suche in einem unsortierten oder sortierten Feld. Danach folgt die binäre Suche, die deutlich effizienter ist und die Folge der Vergleiche in einem binären Baum darstellen kann. Die Interpolationssuche stellt eine mögliche Verbesserung der binären Suche dar und ist besonders für große, gleichmäßig verteilte Felder geeignet. Daraufhin wird die Suche in einem Binärbaum behandelt, der als effiziente und leicht wartbare Datenstruktur dient. Zuletzt werden auch das Löschen von Knoten in einem binären Suchbaum und die Verwendung von indirekten binären Suchbäumen beschrieben.

Die sequentielle Suche in einem unsortierten Feld benötigt N+1 Vergleiche für eine erfolglose Suche und durchschnittlich ungefähr N/2 Vergleiche für eine erfolgreiche Suche. Bei einer sortierten Suche benötigt die sequentielle Suche für beide Fälle ungefähr N/2 Vergleiche. Die binäre Suche hingegen erfordert niemals mehr als lg(N+1) Vergleiche und ist daher deutlich effizienter. Die Interpolationssuche kann für große, gleichmäßig verteilte Felder noch effizienter sein.

Bei der Suche in einem Binärbaum muss man den gesuchten Schlüssel mit der Wurzel vergleichen und dann rekursiv in den entsprechenden Unterbaum gehen, bis die Gleichheit der Schlüssel erreicht ist oder der entsprechende Unterbaum leer ist. Die Suche und das Einfügen in einem binären Suchbaum erfordern durchschnittlich ca. 2 ln N Vergleiche, wenn der Baum aus N zufälligen Schlüsseln aufgebaut ist, während die Laufzeit von Algorithmen, die binäre Suchbäume betreffen, von der Form der Bäume abhängt.

Das Löschen von Knoten aus einem binären Suchbaum ist im Vergleich zur Suche und zum Einfügen komplizierter. Am einfachsten ist das Löschen eines Knotens ohne Nachfolger, beim Löschen von Knoten mit nur einem Nachfolger muss dieser nur ausgekettet und eine Verkettung zwischen dem Vorgänger und dem Nachfolger erstellt werden. Beim Löschen von Knoten mit Nachfolgern, die weitere Nachfolger besitzen, erfolgt das Löschen in drei Schritten.

Indirekte binäre Suchbäume werden nur zum Suchen und nicht zum Herumschieben von Datensätzen genutzt und eignen sich besonders für Felder mit allen Datensätzen mit Schlüsseln.
Direkt das Referat aufrufen

Auszug aus Referat
Elementare Suchmethoden Unter Suchen wird das Wiederauffinden von Information aus einer großen Menge zuvor gespeicherter Informationen verstanden. Normalerweise wird Information in Datensätzen gespeichert, die einen Schlüssel besitzen, nach dem gesucht wird. Das Ziel ist es, alle Elemente aufzufinden, deren Schlüssel mit dem Suchschlüssel übereinstimmt. Das Suchen benötigt bestimmte Datenstrukturen, diese kann man einfach mittels Wörterbüchern erklären. Im Wörterbuch sind die Wörter die Schlüssel, und die Lautschrift, die Definitionen usw. die dazu gespeicherten Informationen. Zur Datenstruktur gehört es aber auch, wie mit gleichen Schlüsseln umgegangen wird. Die erste Möglichkeit ist, in der Primärstruktur keine doppelten Schlüssel zuzulassen. Es ist dann aber notwendig, daß jeder Datensatz in der Primärstruktur eine Verkettung zu einer Liste mit den Datensätzen hat, die diesen Schlüssel haben. In der Primärstruktur könnten aber auch gleiche Schlüssel zugelassen werden. Es muß dann aber gewährleistet sein, alle Daten wieder aufgefunden werden können. Die letzte Möglichkeit besteht auf ein eindeutiges Kennzeichen jedes Datensatzes. 1 Sequentielle Suche Die Daten werden in einem Feld gespeichert, und neue Datensätze am Ende angefügt. Beim Suchen wird jedes Element des Feldes nach dem anderen durchsucht, bis die Suche erfolgreich war, oder das Ende des Feldes erreicht wird. Die sequentielle Suche in einem unsortierten Feld benötigt N 1 Vergleiche für eine erfolglose Suche, ...
Direkt das Referat aufrufen