Robert Sedgewick: Algorithmen

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


14. Elementare Suchmethoden



Suche in einem Binärbaum

Die Suche in einem Binärbaum (binary tree search) ist ein einfaches, effizientes dynamisches Suchverfahren, welches als einer der fundamentalsten Algorithmen in der Informatik betrachtet werden kann. Sie wird hier als »elementare« Methode eingestuft, weil sie so einfach ist; in Wirklichkeit ist sie jedoch in vielen Situationen die bevorzugte Methode.

Wir haben Bäume in Kapitel 4 recht ausführlich betrachtet. Es sei an die Terminologie erinnert: Die zur Definition eines Baumes dienende Eigenschaft ist, daß auf jeden Knoten nur ein anderer Knoten zeigt, der sein (direkter) Vorgänger genannt wird. Die für die Definition eines binären Baumes verwendete Eigenschaft ist, daß jeder Knoten linke und rechte Verkettungen hat. Für die Suche hat jeder Knoten auch einen Datensatz mit einem Schlüsselwert; in einem binären Suchbaum fordern wir, daß sich alle Datensätze mit kleineren Schlüsselwerten im linken Unterbaum befinden, und daß alle Datensätze im rechten Unterbaum größere (oder gleiche) Schlüsselwerte haben. Wir werden bald sehen, daß es sehr einfach ist zu gewährleisten, daß binäre Suchbäume, die durch sukzessives Einfügen von neuen Knoten aufgebaut werden, diese definierende Eigenschaft besitzen. Ein Beispiel eines binären Suchbaums zeigt Abbildung 14.6; leere Unterbäume sind wie gewöhnlich durch Knoten in Form kleiner Quadrate dargestellt.

Abbildung 14.6
Abbildung 14.6 Ein binärer Suchbaum.

Eine Suchprozedur wie binarysearch bietet sich für diese Struktur sofort an. Um einen Datensatz mit einem gegebenen Schlüssel v zu finden, vergleiche ihn zuerst mit der Wurzel. Wenn er kleiner ist, gehe zum linken Unterbaum; wenn Gleichheit gilt, brich ab; wenn er größer ist, gehe zum rechten Unterbaum. Wende diese Methode rekursiv an. Bei jedem Schritt haben wir die Gewähr, daß kein Teil des Baumes außer dem aktuellen Unterbaum Datensätze mit dem Schlüssel v enthalten kann, und ebenso, wie die Größe des Intervalls bei der binären Suche abnimmt, wird der »aktuelle Unterbaum« immer kleiner. Die Prozedur bricht entweder dann ab, wenn ein Datensatz mit dem Schlüssel v gefunden wird, oder, falls ein solcher Datensatz nicht existiert, dann, wenn der »aktuelle Unterbaum« leer wird. (Die Wörter »binär«, »Suche« und »Baum« werden an dieser Stelle tatsächlich etwas überstrapaziert, und der Leser sollte darauf achten, daß er den Unterschied zwischen der weiter vorn in diesem Kapitel angegebenen Funktion binarysearch und den hier beschriebenen binären Suchbäumen versteht. Bei der binären Suche verwendeten wir einen binären Baum, um die Folge von Vergleichen zu beschreiben, die von einer in einem Feld suchenden Funktion ausgeführt werden; hier bauen wir eine Datenstruktur aus Datensätzen auf, die durch Verkettungen verbunden sind, und benutzen sie für die Suche.)

    type link=^.node;
         node=record key,info: integer; l,r: link end;
    var t,head,z: link;
    function treesearch(v: integer; x: link): link;
      begin
      z^.key:=v;
      repeat
        if v<x^.key then x:=x.l else x:=x^.r
      until v=x^.key;
      treesearch:=x
      end;

Es ist zweckmäßig, im Baum einen Kopfknoten head zu verwenden, dessen rechte Verkettung auf den eigentlichen Wurzelknoten des Baums zeigt und dessen Schlüssel kleiner ist als alle anderen Schlüsselwerte (der Einfachheit halber verwenden wir 0, wobei wir annehmen, daß alle Schlüssel positive ganze Zahlen sind). Die linke Verkettung von head wird nicht benutzt. Die Notwendigkeit von head wird weiter unten deutlicher werden, wenn wir das Einfügen erörtern.

Um einen Datensatz mit dem Schlüssel v zu suchen, setzen wir x:=treesearch (v, head). Falls ein Knoten keinen linken (rechten) Unterbaum hat, so wird seine linke (rechte) Verkettung so gesetzt, daß sie auf einen »Endknoten« z zeigt. Wie bei der sequentiellen Suche setzen wir den gesuchten Wert in z, um eine erfolglose Suche abzubrechen. Daher wird der »aktuelle Unterbaum«, auf den x zeigt, niemals leer, und alle Suchvorgänge sind »erfolgreich«: Das aufrufende Programm kann prüfen, ob die zurückgegebene Verkettung auf z zeigt, um festzustellen, ob die Suche erfolgreich war.

Wie oben in Abbildung 14.6 dargestellt, ist es zweckmäßig, sich die Verkettungen, die auf z zeigen, als auf imaginäre äußere Knoten zeigend vorzustellen, wobei alle erfolglosen Suchvorgänge bei äußeren Knoten enden. Die normalen Knoten, die unsere Schlüssel enthalten, werden innere Knoten genannt; durch die Einführung äußerer Knoten können wir sagen, daß jeder innere Knoten auf zwei andere Knoten im Baum zeigt, auch wenn in unserer Implementation alle äußeren Knoten durch den einzigen Knoten z dargestellt werden. Abbildung 14.7 zeigt diese Verkettungen und die Pseudoknoten explizit.

Abbildung 14.7
Abbildung 14.7 Ein binärer Suchbaum (mit Pseudoknoten).

Der leere Baum wird dargestellt, indem man die rechte Verkettung von head auf z zeigen läßt, wie es durch das folgende Programm realisiert wird:

    procedure treeinitialize;
      begin
      new(z); z^.l:=z; z^.r:=z;
      new(head); head^.key:=0; head^.r:=z;
      end;

Hierdurch werden die Verkettungen von z so initialisiert, daß sie auf z selbst zeigen; obwohl die Programme in diesem Kapitel niemals auf die Verkettungen von z zugreifen, ist diese Initialisierung »sicher« und zweckmäßig für die weiterentwickelten Programme, die wir später betrachten werden.

Abbildung 14.8 zeigt, was passiert, wenn in unserem Beispielbaum unter Verwendung von treesearch ein I gesucht wird. Zuerst wird es mit A verglichen, dem Schlüssel an der Wurzel. Da I größer ist, wird es danach mit S verglichen, dem Schlüssel im rechten Nachfolger des Knotens, der A enthält. Indem in dieser Weise fortgefahren wird, wird I daraufhin mit dem E links von diesem Knoten verglichen, dann mit R, dann mit H. Die Verkettungen in dem H enthaltenden Knoten sind Zeiger, die auf z weisen, so daß die Suche abbricht: I wird in z mit sich selbst verglichen, und die Suche ist erfolglos.

Abbildung 14.8
Abbildung 14.8 Suchen (nach I) in einem binären Suchbaum.

Um einen Knoten in den Baum einzufügen, führen wir eine erfolglose Suche nach diesem Knoten durch und ordnen ihn dann anstelle von z dort an, wo die Suche beendet wurde. Um das Einfügen auszuführen, verfolgt das folgende Programm den Vorgänger p von x, während es sich im Baum abwärts bewegt. Wenn die unterste Ebene des Baumes (x=z) erreicht ist, zeigt p auf den Knoten, dessen Verkettung so geändert werden muß, daß sie auf den eingefügten neuen Knoten zeigt.

    function treeinsert(v: integer; x:link): link;
      var p: link;
      begin
      repeat
        p:=x;
        if v<x^.key then x:=x^.l else x:=x^.r
      until x=z;
      new(x); x^.key:=v; x^.l:=z; x^.r:=z;
      if v<p^.key then p^.l:=x else p^.r:=x;
      treeinsert:=x
      end;

Ein Schlüssel v kann hinzugefügt werden, indem der Aufruf treeinsert (v, head) benutzt wird. Diese Funktion gibt eine auf den neu erzeugten Knoten weisende Verkettung zurück, so daß die aufrufende Routine das Feld info in geeigneter Weise ausfüllen kann.

Wenn ein neuer Knoten eingefügt wird, dessen Schlüssel mit einem bereits im Baum vorhandenen Schlüssel übereinstimmt, so wird er rechts von dem schon im Baum befindlichen Knoten eingefügt. Alle Datensätze, deren Schlüssel mit v übereinstimmen, können somit verarbeitet werden, indem sukzessive t gleich search (v, t) gesetzt wird, wie wir es bei der sequentiellen Suche getan haben.

Der Baum in Abbildung 14.9 ergibt sich, wenn die Schlüssel A S E A R C H I in einen ursprünglich leeren Baum eingefügt werden; Abbildung 14.10 zeigt die Vervollständigung unseres Beispiels, wenn N G E X A M P L E hinzugefügt werden. Der Leser sollte der Position gleicher Schlüssel in diesem Baum besondere Aufmerksamkeit schenken: Obwohl zum Beispiel die drei »A« über den ganzen Baum verteilt zu sein scheinen, gibt es keine Schlüssel »zwischen« ihnen.

Abbildung 14.9
Abbildung 14.9 Einfügen (von l) in einem binären Suchbaum.

Abbildung 14.10
Abbildung 14.10 Aufbauen eines binären Suchbaumes.

Die sort-Funktion erhält man bei Verwendung binärer Suchbäume nahezu gratis, da ein binärer Suchbaum eine sortierte Datei darstellt, wenn man ihn in der richtigen Weise betrachtet. In unseren Abbildungen erscheinen die Schlüssel in der richtigen Reihenfolge, wenn sie im Bild von links nach rechts gelesen werden (wobei ihre Höhe und die Verkettungen zu ignorieren sind). Ein Programm kann nur mit den Verkettungen arbeiten, doch eine Sortiermethode folgt unmittelbar aus den definierenden Eigenschaften binärer Suchbäume. Das folgende Programm zur Traversierung in der richtigen Reihenfolge löst die Aufgabe (siehe Kapitel 4):

    procedure treeprint(x: link);
      begin
      if x<>z then
        begin
        treeprint(x^.l);
        printnode(x);
        treeprint(x^.r)
        end
      end;

Der Aufruf treeprint (head^.r) bewirkt die Ausgabe der Schlüssel des Baumes in der richtigen Reihenfolge. Hierdurch wird eine Sortiermethode definiert, die eine bemerkenswerte Ähnlichkeit mit Quicksort besitzt, wobei der Knoten an der Wurzel des Baumes eine ähnliche Rolle spielt wie das zerlegende Element in Quicksort. Ein Hauptunterschied besteht darin, daß bei der Baum-Sortiermethode zusätzlicher Speicherplatz für die Verkettungen benutzt werden muß, während Quicksort mit nur wenig zusätzlichem Speicherplatz sortiert.

Die Laufzeiten von Algorithmen, die binäre Suchbäume betreffen, sind stark von der Form der Bäume abhängig. Im günstigsten Fall könnte der Baum eine Gestalt wie in der Abbildung 14.3 haben, mit ungefähr lg N Knoten zwischen der Wurzel und jedem äußeren Knoten. Wir könnten dann im Durchschnitt mit annähernd logarithmischen Suchzeiten rechnen, da das erste eingefügte Element zur Wurzel des Baumes wird; falls N zufällige Schlüssel einzufügen sind, würde dieses Element die Schlüssel (im Durchschnitt) in zwei Hälften teilen, und dies würde zu logarithmischen Suchzeiten führen (durch Anwendung der gleichen Überlegung auf die Unterbäume). Wäre da nicht die Möglichkeit des Auftretens gleicher Schlüssel, so könnte tatsächlich der Baum erzeugt werden, den wir weiter oben zur Beschreibung der Struktur der Vergleiche bei der binären Suche vorgestellt haben. Dies wäre der günstigste Fall des Algorithmus, mit garantiert logarithmischer Laufzeit für alle Suchvorgänge. In Wirklichkeit kann in einer echten zufälligen Situation jeder beliebige Schlüssel mit gleicher Wahrscheinlichkeit die Wurzel sein, so daß ein solcher vollkommen ausgeglichener Baum äußerst selten ist. Wenn jedoch zufällige Schlüssel eingefügt werden, erweist es sich, daß die Bäume recht gut ausgeglichen sind.

Eigenschaft 14.5 Ein Suchen oder Einfügen in einem binären Suchbaum erfordert durchschnittlich ungefähr 2 ln N Vergleiche, wenn der Baum aus N zufälligen Schlüsseln aufgebaut ist.

Für jeden Knoten im Baum ist die Anzahl der Vergleiche, die für eine erfolgreiche Suche dieses Knotens benötigt wird, gleich seinem Abstand von der Wurzel. Die Summe dieser Abstände für alle Knoten wird die innere Pfadlänge des Baumes genannt. Indem wir die innere Pfadlänge durch N dividieren, erhalten wir die durchschnittliche Anzahl der für eine erfolgreiche Suche erforderlichen Vergleiche. Wenn wir nun mit CN die durchschnittliche innere Pfadlänge eines binären Suchbaums mit N Knoten bezeichnen, erhalten wir die rekurrente Beziehung

Formel

mit C1 = 1. (Die Größe N - 1 drückt die Tatsache aus, daß die Wurzel zur Pfadlänge von jedem der anderen N - 1 Knoten im Baum 1 hinzufügt; der restliche Teil des Ausdrucks ergibt sich aus der Beobachtung, daß der Schlüssel an der Wurzel (der zuerst eingefügte) mit gleicher Wahrscheinlichkeit der k-größte ist, wobei sich zufällige Unterbäume der Größe k - 1 und N - k ergeben.) Doch dies ist beinahe dieselbe rekurrente Beziehung, die wir in Kapitel 9 für Quicksort gelöst haben, und sie kann leicht in der gleichen Weise aufgelöst werden, um die Behauptung herzuleiten. Die Überlegungen für den Fall einer erfolglosen Suche sind ähnlich, wenn auch etwas komplizierter. w.z.b.w.

Abbildung 14.11 zeigt einen großen binären Suchbaum, der aus einer zufälligen Permutation von 95 Elementen erzeugt wurde. Obwohl er einige kurze Pfade und einige lange Pfade besitzt, kann er als recht gut ausgeglichen bezeichnet werden; jede Suche würde weniger als zwölf Vergleiche erfordern, und die »durchschnittliche« Anzahl von Vergleichen für das Auffinden eines beliebigen Schlüssels im Baum beträgt 7,00, im Vergleich zu 5,74 für die binäre Suche. (Die durchschnittliche Anzahl von Vergleichen für eine zufällige erfolglose Suche ist um eins größer als für eine erfolgreiche Suche.) Darüber hinaus kann ein neuer Schlüssel ungefähr mit dem gleichen Aufwand eingefügt werden, was eine Flexibilität bedeutet, die bei der binären Suche nicht vorhanden ist. Wenn die Schlüssel allerdings nicht zufällig geordnet sind, arbeitet der Algorithmus eventuell sehr schlecht.

Abbildung 14.11
Abbildung 14.11 Ein umfangreicher binärer Suchbaum.

Eigenschaft 14.6 Im ungünstigsten Fall kann eine Suche in einem binären Suchbaum mit N Schlüsseln N Vergleiche erfordern.

Wenn zum Beispiel die Schlüssel in geordneter Reihenfolge (oder in umgekehrter Reihenfolge) eingefügt werden, ist die Methode der Suche in einem Binärbaum nicht besser als das sequentielle Suchverfahren, das wir zu Beginn dieses Kapitels betrachtet haben. Darüber hinaus gibt es viele andere entartete Baumarten, die zu dem gleichen ungünstigsten Fall führen können (man betrachte zum Beispiel den Baum, der gebildet wird, wenn die Schlüssel A Z B Y C X ... in der angegebenen Reihenfolge in einen ursprünglich leeren Baum eingefügt werden). Im nächsten Kapitel betrachten wir eine Methode, mit der dieser ungünstigste Fall ausgeschlossen und mit der erreicht wird, daß alle Bäume eher dem Baum für den besten Fall ähneln. w.z.b.w.


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