Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


14. Elementare Suchmethoden



Indirekte binäre Suchbäume

Wie wir in Kapitel 11 bei Heaps gesehen haben, benötigen wir für viele Anwendungen eine Suchstruktur einfach dafür, daß sie uns hilft, Datensätze zu finden, und nicht, um sie umherzubewegen. Zum Beispiel könnte es sein, daß wir ein Feld a[1..N] von Datensätzen mit Schlüsseln haben und möchten, daß die search-Routine uns den Feldindex des Datensatzes angibt, der mit einem bestimmten Schlüssel übereinstimmt. Oder wir könnten beabsichtigen, den Datensatz mit einem gegebenen Index aus der Suchstruktur zu entfernen, ihn aber für einen anderen Zweck noch im Feld zu belassen.

Um binäre Suchbäume an eine solche Situation anzupassen, machen wir einfach das Feld info der Knoten zum Feldindex. Dann können wir das Feld key (Schlüssel) eliminieren, indem wir die Suchroutinen direkt auf die Schlüssel in den Datensätzen zugreifen lassen, d. h., über eine Anweisung der Art if v < a[x^.info] then... Es ist jedoch oft besser, eine Kopie des Schlüssels anzulegen und das obige Programm in der gegebenen Form zu benutzen. Wir werden den Funktionsnamen bstinsert(v, info: integer; x: link) verwenden, um eine Funktion zu bezeichnen, die mit treeinsert übereinstimmt, jedoch auch das Feld info auf den im Argument angegebenen Wert setzt. In ähnlicher Weise soll eine Funktion bstdelete(v, info: integer; x: link) zum Löschen des Knotens mit dem Schlüssel v und dem Feldindex info aus dem binären Suchbaum mit der Wurzel x eine Implementation der Funktion delete in der oben beschriebenen Weise bezeichnen. Diese Funktionen benutzen eine zusätzliche Kopie der Schlüssel (eine im Feld, eine im Baum), doch dadurch erhält man die Möglichkeit, die gleiche Funktion für mehr als ein Feld zu verwenden oder, wie wir in Kapitel 27 sehen werden, für mehr als ein Schlüsselfeld im gleichen Feld. (Es gibt noch andere Wege, um das zu erreichen: Zum Beispiel könnte mit jedem Baum eine Prozedur verknüpft werden, welche Schlüssel aus Datensätzen extrahiert.)

Ein anderer direkter Weg, »Indirektheit« für binäre Suchbäume zu erreichen, besteht einfach darin, völlig auf die Implementation mit Verkettungen zu verzichten. Das heißt, daß alle Verkettungen einfach zu Indizes werden, die auf ein Feld a[1..N] von Datensätzen zeigen, die ein Feld key (Schlüssel) und Indexfelder l und r enthalten. Dann werden Bezugnahmen auf Verkettungen von der Art if v < x^.key then x:=xI^.l else ... zu Bezugnahmen auf das Feld von der Art if v < a[x].key then x:=a[x].l else... Es werden keine Aufrufe von new verwendet, da der Baum innerhalb des Feldes von Datensätzen existiert: new (head) wird zu head:=0, new (z) wird zu N := N + 1; z := N. Um den M-ten Knoten einzufügen, würden wir M und nicht v an treeinsert übergeben und dann einfach auf a[M].key anstelle auf v Bezug nehmen und die new(x) enthaltende Zeile in treeinsert durch x:=M ersetzen.

Diese Methode der Implementation binärer Suchbäume, die das Durchsuchen großer Felder von Datensätzen erleichtern soll, wird bei vielen Anwendungen bevorzugt, da hierdurch der zusätzliche Aufwand des Kopierens von Schlüsseln wie im vorangegangenen Abschnitt vermieden wird, und da der Ballast des Speicherzuweisungsmechanismus vermieden wird, der durch new entsteht. Ihr Nachteil liegt darin, daß durch unbenutzte Verkettungen Platz im Feld vergeudet werden könnte.

Eine dritte Alternative besteht in der Verwendung von parallelen Feldern, wie wir es in Kapitel 3 für verkettete Listen getan haben. Die Implementation dieser Methode erfolgt in ähnlicher Weise wie im vorangegangenen Absatz beschrieben, abgesehen davon, daß drei Felder verwendet werden, jeweils eins für die Schlüssel, die linken und die rechten Verkettungen. Der Vorteil dieser Methode ist ihre Flexibilität. Zusätzliche Felder (mit jedem Knoten verknüpfte zusätzliche Informationen) können leicht hinzugefügt werden, ohne daß das Programm für die Baumoperationen überhaupt geändert werden muß, und wenn die Suchroutine den Index für einen Knoten angibt, so gibt die Methode die Möglichkeit, sofort auf alle Felder zuzugreifen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]