Robert Sedgewick: Algorithmen

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


17. Digitales Suchen



Digitale Suchbäume

Das einfachste digitale Suchverfahren ist die Suche mit digitalen Bäumen; der Algorithmus ist genau der gleiche wie der für die Suche in einem Binärbaum, mit dem Unterschied, daß wir in dem Baum nicht entsprechend dem Ergebnis des Vergleiches zwischen den Schlüsseln verzweigen, sondern entsprechend den Bits des Schlüssels. Auf der ersten Ebene wird das führende Bit benutzt, auf der zweiten Ebene das zweite führende Bit usw., bis ein äußerer Knoten vorgefunden wird. Das Programm hierfür ist praktisch das gleiche wie für die Suche in einem Binärbaum. Der einzige Unterschied ist, daß die Vergleiche der Schlüssel durch Aufrufe der Funktion bits ersetzt werden, die wir beim digitalen Sortieren verwendet haben. (Wir erinnern daran, daß gemäß Kapitel 10 bits(x, k, j) die j Bits bezeichnet, die k Stellen von rechts erscheinen; die Funktion kann in Maschinensprache effizient implementiert werden, indem um k Bits nach rechts geschoben wird und dann alle Bits außer den rechts befindlichen j Bits auf 0 gesetzt werden.)

    function digitalsearch(v: integer; x: link): link;
      var b: integer;
      begin
      z^.key:=v; b:=maxb;
      repeat
        if bits(v,b,1)=0 then x:=x^.l else x:=x^.r;
        b:=b-1;
      until v=x^.key;
      digitalsearch:=x
      end;

Die Datenstrukturen für dieses Programm sind die gleichen wie die, die wir für elementare binäre Suchbäume benutzt haben. Die Konstante maxb ist die Anzahl der Bits in den Schlüsseln, die zu sortieren sind. Für das Programm wird angenommen, daß das erste Bit in jedem Schlüssel (das (maxb+1)-te von rechts) 0 ist (vielleicht ist der Schlüssel das Ergebnis eines Aufrufs von bits mit einem dritten Argument maxb), so daß die Suche erfolgt, indem x:=digitalsearch(v, head) gesetzt wird, wobei head eine Verkettung ist, die auf den Kopfknoten eines Baumes mit dem Schlüssel 0 und mit einer auf den Suchbaum zeigenden linken Verkettung zeigt. Daher ist die Prozedur zur Initialisierung für dieses Programm die gleiche wie für die Suche in einem Binärbaum, abgesehen davon, daß wir mit head^.l:=z anstatt mit head^.r:=z beginnen.

In Kapitel 10 haben wir gesehen, daß gleiche Schlüssel beim digitalen Sortieren ein Problem sind; das gleiche gilt bei der digitalen Suche, nicht bei diesem speziellen Algorithmus, sondern bei denen, die wir später untersuchen wollen. Wir setzen daher in diesem Kapitel voraus, daß alle Schlüssel, die in der Datenstruktur auftreten, unterschiedlich sind; falls erforderlich könnte für jeden Schlüsselwert eine verkettete Liste der Datensätze, deren Schlüssel den betreffenden Wert haben, geführt werden. Wie in den vorangegangenen Kapiteln nehmen wir an, daß der i-te Buchstabe des Alphabets durch die aus fünf Bits bestehende Binärdarstellung von i repräsentiert wird. Die Beispielschlüssel, die in diesem Kapitel verwendet werden sollen, sind in Abbildung 17.1 angegeben. Um Konsistenz mit bits zu erreichen, betrachten wir die Bits als von rechts nach links mit 0 bis 4 durchnumeriert. Demnach ist Bit 0 das einzige von 0 verschiedene Bit von A, und Bit 4 ist das einzige von 0 verschiedene Bit von P.

Abbildung 17.1
Abbildung 17.1 Ein digitaler Suchbaum.

Die Prozedur für das Einfügen in digitale Suchbäume läßt sich gleichfalls unmittelbar aus der entsprechenden Prozedur für binäre Suchbäume ableiten:

    function digitalinsert(v: integer; x: link): link;
      var p: link; b: integer;
      begin
      b:=maxb;
      repeat
        p:=x;
        if bits(v,b,1)=0 then x:=x^.l else x:=x^.r;
        b:=b-1;
      until x=z;
      new(x); x^.key:=v; x^.l:=z; x^.r:=z;
      if bits(v,b+1,1)=0 then p^.l:=x else p^.r:=x;
      digitalinsert:=x
      end;

Der Baum, der mit Hilfe dieses Programms erzeugt wird, wenn unsere Beispielschlüssel in einen ursprünglich leeren Baum eingefügt werden, ist in Abbildung 17.1 dargestellt. Abbildung 17.2 zeigt, was passiert, wenn ein neuer Schlüssel Z=11010 zu dem Baum in Abbildung 17.1 hinzugefügt wird. Wir wenden uns zweimal nach rechts, da die beiden führenden Bits von Z 1 sind, und wenden uns dann nach links, wo wir den äußeren Knoten links von X vorfinden, wo Z eingefügt wird.

Abbildung 17.2
Abbildung 17.2 Einfügen (von Z) in einen digitalen Suchbaum.

Der ungünstigste Fall für Bäume, die mit digitaler Suche erzeugt werden, ist viel besser als für binäre Suchbäume, wenn die Anzahl der Schlüssel groß ist und die Schlüssel nicht lang sind. Die Länge des längsten Pfades in einem digitalen Suchbaum ist gleich der längsten Übereinstimmung in den führenden Bits zwischen zwei beliebigen Schlüsseln im Baum, und diese ist für viele Anwendungen meist relativ klein (zum Beispiel wenn die Schlüssel aus zufälligen Bits bestehen).

Eigenschaft 17.1 Ein Suchen oder Einfügen in einem digitalen Suchbaum erfordert durchschnittlich ungefähr lg N Vergleiche und im ungünstigsten Fall b Vergleiche, wenn der Baum aus N zufälligen Schlüsseln mit b Bits erzeugt wurde.

Es ist offensichtlich, daß kein Pfad jemals länger sein kann als die Anzahl der Bits in den Schlüsseln; zum Beispiel kann ein digitaler Suchbaum, der aus Schlüsseln mit acht Zeichen erzeugt wurde, mit beispielsweise sechs Bits pro Zeichen, keinen Pfad besitzen, der länger als 48 ist, selbst wenn es Hunderttausende von Schlüsseln gibt. Das Ergebnis, daß digitale Suchbäume im Durchschnitt nahezu perfekt ausgeglichen sind, erfordert eine Analyse, die über den Rahmen dieses Buches hinausgehen würde, obwohl es der einfachen intuitiven Überlegung entspricht, daß das »nächste« Bit eines zufälligen Schlüssels mit der gleichen Wahrscheinlichkeit 0 wie 1 sein kann, so daß auf beide Seiten eines jeden Knotens jeweils die Hälfte entfällt. Abbildung 17.3 zeigt einen digitalen Suchbaum, der aus 95 zufälligen Schlüsseln mit je 7 Bits erzeugt wurde; dieser Baum ist sehr gut ausgeglichen. w.z.b.w.

Abbildung 17.3
Abbildung 17.3 Ein umfangreicher digitaler Suchbaum.

Demzufolge stellen digitale Suchbäume eine interessante Alternative zu gewöhnlichen binären Suchbäumen dar, vorausgesetzt, daß sich das Extrahieren von Bits ebenso leicht realisieren läßt wie der Vergleich von Schlüsseln (was in Pascal eigentlich nicht der Fall ist).


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