Elementare suchmethoden
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.
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, und durchschnittlich ungefähr N/2 Vergleiche für eine erfolgreiche Suche.
Verwendet man ein sortiertes Feld, so kann die Suche als erfolglos abgebrochen werden, wenn ein Schlüssel gefunden wird, der größer als der gesuchte Schlüssel ist.
Die sequentielle Suche in einem sortierten Feld benötigt sowohl für eine erfolgreiche aber auch für die erfolglose Suche ungefähr N/2 Vergleiche.
Um die Suche zu beschleunigen kann man die am häufigsten benötigten Datensätze an den Beginn des Feldes stellen.
Ist keine Information über die Häufigkeit vorhanden, kann man den zuletzt gesuchten Datensatz an den Beginn des Feldes stellen. Dies ist dann besonders effizient, wenn die meisten Zugriffe auf einen Datensatz eng aufeinander folgen.
Binäre Suche (binary search)
Die Suchzeit kann gegenüber der sequentiellen Suche verringert werden, indem man ein sortiertes Feld durchsucht. Das Feld wird in zwei Hälften geteilt, und festgestellt in welcher Hälfte des Feldes sich der gesuchte Datensatz befindet. Diese Methode wird dann rekursiv angewandt, bis nur mehr ein Datensatz übrig ist. Dieser kann der gesuchte sein, oder den Datensatz mit dem gesuchten Schlüssel gibt es nicht.
Im Beispiel wird nach der Zahl 13 gesucht:
Binäre Suche erfordert sowohl für erfolgreiche als auch für erfolglose Suche niemals mehr als lg(N+1) Vergleiche.
Dies gilt, weil bei jedem Schritt die Anzahl der Datensätze halbiert wird. Ein Problem entsteht bei nicht eindeutigen Schlüsseln. Wenn während der Suche ein gesuchter Datensatz gefunden wird, müssen dann nämlich auch dessen Nachbarn durchsucht werden.
Die Folge der Vergleiche ist beim binären Suchen vorbestimmt, und kann in einem binären Baum dargestellt werden. Später werden noch Algorithmen beschrieben, die speziell konstruierte Baumstrukturen zur Steuerung der Suche benötigen.
Interpolationssuche (interpolation search)
Diese stellt eine mögliche Verbesserung dar. Hier versucht man genauer zu erraten, wo sich das gesuchte Element befindet. Dies erinnert an die Suche in einem Telefonbuch, wo man eher vorne zu suchen beginnt, wenn der gesuchte Name mit einem B beginnt. Im Beispiel wird wieder nach der 13 gesucht:
Interpolationssuche erfordert für erfolgreiche aber auch für erfolglose Suche niemals mehr als lg[lg(N+1)] Vergleiche.
Die Interpolationssuche ist besonders für große, gleichmäßig verteilte Felder geeignet, da z. B.
für eine Milliarde Elemente nur maximal 5 Schritte erforderlich wären. Ein Nachteil ist, das die Interpolationssuche bei einer sehr ungleichmäßigen Verteilung hereingelegt werden kann. Bei kleinen Feldern ist auch der Vorteil der durch die Interpolation entsteht sehr gering.
Suche in einem Binärbaum (binary tree search)
Wie bereits bekannt ist, kann man die Folge der Vergleiche des binären Suchens in einem binären Baum darstellen. Die Idee ist nun, die Daten in einem Baum durch Verkettung zu speichern. Der Vorteil gegenüber der binären Suche ist, daß die Datenstruktur immer leicht wartbar ist.
Es ist einfach ein neues Element einzubinden und ohne kompliziertes Herumschieben von Daten ist immer eine sortierte Struktur vorhanden.
Sie ist eine der fundamentalsten Methoden der Informatik. Trotz ihrer Einfachheit ist sie effizient, und wird daher sehr oft eingesetzt.
Ein Baum ist dadurch definiert, daß jedes Glied genau ein übergeordnetes hat. Ein binärer Baum hat zusätzlich noch die Eigenschaft, daß jeder Knoten eine linke und eine rechte Verkettung hat. Beim binären Suchen wird weiters davon ausgegangen, daß alle Datensätze mit einem kleineren Schlüssel im linken Unterbaum und alle größeren und gleichen im rechten Unterbaum sind.
Bei der Suche vergleicht man den gesuchten Schlüssel mit der Wurzel, und geht dann in den entsprechenden Unterbaum, wo diese Vergleiche rekursiv fortgesetzt werden, bis die Gleichheit der Schlüssel erreicht ist, oder wenn der entsprechende Unterbaum leer ist.
Um einen Knoten hinzuzufügen, verfährt man wie beim erfolglosen Suchen, nur wird dann der leere Unterbaum durch den einzufügenden Knoten (I) ersetzt.
Ein Suchen oder Einfügen in einem binären Suchbaum erfordert durchschnittlich ca. 2 ln N Vergleiche, wenn der Baum aus N zufälligen Schlüsseln aufgebaut ist.
Die Laufzeit von Algorithmen, die binäre Suchbäume betreffen sind stark von der Form der Bäume abhängig. Bei ausgeglichenen Bäumen kann sie sogar logarithmisch werden.
Durch die Art des Aufbauens der Bäume können aber auch extrem ungünstige Bäume entstehen (A Z B Y C X ... oder A B C D E F ...
).
Im ungünstigsten Fall kann eine Suche in einem binären Suchbaum mit N Schlüsseln N Vergleiche erfordern.
Löschen
Die bis jetzt behandelten Algorithmen waren recht unkompliziert im Vergleich zum Löschen einzelner Elemente aus einem binären Suchbaum. Hier kommt es nämlich darauf an, wo sich der Knoten befindet bzw. wieviele Nachfolger er hat. Hierzu ein Beispiel:
Am einfachsten ist das Löschen eines Knotens ohne Nachfolger (C, L, P), weil nur eine Verkettung gelöscht werden muß.
Beim Löschen von Knoten mit nur einem Nachfolger (A, R, H, M) muß dieser nur ausgekettet, und eine Verkettung zwischen dem Vorgänger und dem Nachfolger erstellt werden.
Auch das Löschen eines Knotens, von dem einer der Nachfolger keinen Nachfolger hat (N), ist kein Problem, da man den Knoten durch diesen Nachfolger ersetzen kann.
Das einzige Problem kann es weiter oben im Baum geben, wo jeder Nachfolger weitere Nachfolger besitzt. Das Löschen eines solchen Knotens (E) erfolgt in drei Schritten:
Suchen des nächstgrößeren Knotens (H); dieser kann nur einen Nachfolger haben
Ausgeketten dieses Knotens; nach den oben genannten Methoden
Ersetzen des zu löschenden Knotens durch den größeren
Nachteil dieser Funktion ist, daß bei vielen „Löschen - Einfügen“ Paaren ein leicht unausgeglichener Baum entsteht. Dieses Problem kann man mittels „lazy deletion“ lösen. Hier wird ein Knoten nicht wirklich gelöscht, sondern nur als gelöscht markiert, und dadurch die Baumstruktur erhalten.
Das Problem, das dabei entsteht, ist die Vergeudung der Zeit. Dies kann durch regelmäßiges Neuaufbauen des Baumes, mit Weglassen der markierten Knoten verhindert werden.
Indirekte binäre Suchbäume
Für viele Anwendungen benötigt man die Suchstruktur ausschließlich zum Suchen, und nicht zum Herumschieben von Datensätzen. Ein Beispiel wäre ein Feld mit allen Datensätzen mit Schlüsseln. Hier könnte man den Feldindex des Datensatzes suchen, der mit einem bestimmten Schlüssel übereinstimmt. So könnte man auch einen Datensatz mit einem bestimmten Index aus der Suchstruktur entfernen, ihn aber trotzdem noch im Feld behalten.
Ein Weg zur Indirektheit wäre, wenn man auf die Verkettung zugunsten eines Feld verzichtet. Im Feld müssen dann die drei folgenden Attribute vorhanden sein:
Schlüssel
linker Nachfolger
rechter Nachfolger
Diese Methode wird oft bevorzugt, da man sich das Speicherzuweisen erspart. Der Nachteil ist, das unbenutzte Verkettungen Platz im Feld vergeuden.
Die zweite Möglichkeit liegt in der Festlegung von drei Feldern für Schlüssel, linker und rechter Nachfolger. Man kann leicht zusätzliche Felder (Information) hinzufügen, ohne das Programm für die Baumoperationen ändern zu müssen. Der Zugriff auf solche Felder erfolgt über den Index.
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
