Robert Sedgewick: Algorithmen

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


26. Bereichssuche



Wenn eine Menge von Punkten gegeben ist, ist es natürlich, danach zu fragen, welcher dieser Punkte auf ein bestimmtes vorgegebenes Gebiet entfällt. »Aufzählen aller Städte, die im Umkreis von 50 Meilen um Princeton liegen« ist eine Frage dieses Typs, die zu stellen sinnvoll wäre, wenn eine Menge von den Städten der USA entsprechenden Punkten zur Verfügung stünde. Wenn die geometrische Form dahingehend eingeschränkt wird, daß es sich um ein Rechteck handelt, läßt sich die Frage mühelos auf nichtgeometrische Probleme übertragen. Zum Beispiel entspricht die Forderung »Aufzählen aller Personen zwischen 21 und 25 mit Einkommen zwischen 60.000 $ und 100.000 $« der Frage, welche »Punkte« aus einer Datei, die Namen, Altersangaben und Einkommen von Personen enthält, auf ein bestimmtes Rechteck im Alter-Einkommen-Diagramm entfallen.

Eine Übertragung auf mehr als zwei Dimensionen ist ebenso möglich. Wenn wir alle Sterne im Umkreis von 50 Lichtjahren um die Sonne aufzählen wollen, so liegt ein dreidimensionales Problem vor, und wenn wir möchten, daß die reichen jungen Leute aus dem obigen Absatz zusätzlich noch groß und weiblich sind, so haben wir ein vierdimensionales Problem. Die Dimension solcher Probleme kann beliebig hoch werden.

Im allgemeinen setzen wir voraus, daß wir eine Menge von Datensätzen (records) mit gewissen Attributen haben, die Werte aus einer bestimmten geordneten Menge annehmen. (Dies wird manchmal eine Datenbank genannt, obwohl spezifischere und vollständigere Definitionen für diesen wichtigen Begriff entwickelt worden sind.) Das Auffinden aller Datensätze in einer Datenbank, die bestimmten Bereichsbeschränkungen einer vorgegebenen Menge von Attributen genügen, wird Bereichssuche (range searching) genannt und stellt ein kompliziertes und wichtiges Problem in praktischen Anwendungen dar. Im vorliegenden Kapitel konzentrieren wir uns auf das zweidimensionale geometrische Problem, in dem die Datensätze Punkte und die Attribute ihre Koordinaten sind, und erörtern dann geeignete Verallgemeinerungen.

Die Verfahren, die wir betrachten wollen, sind unmittelbare Verallgemeinerungen von Methoden, die wir für das Suchen mit einfachen Schlüsseln (im eindimensionalen Fall) kennengelernt haben. Wir setzen voraus, daß viele Anfragen betreffs der gleichen Punktmenge zu erwarten sind, so daß das Problem in zwei Teile zerfällt: Wir benötigen einen Algorithmus für die Vorverarbeitung, der aus den gegebenen Punkten eine Struktur aufbaut, die eine effiziente Bereichssuche unterstützt, und einen Algorithmus für die Bereichssuche, der die Struktur verwendet, um Punkte zurückzugeben, die einem beliebigen gegebenen (mehrdimensionalen) Bereich angehören. Diese Trennung erschwert den Vergleich zwischen verschiedenen Verfahren, da die Gesamtkosten nicht nur von der Verteilung der betreffenden Punkte abhängen, sondern auch von der Anzahl und Art der Anfragen.

Das Problem der Bereichssuche im eindimensionalen Fall besteht darin, alle Punkte zurückzugeben, die in einem vorgegebenen Intervall liegen. Dies läßt sich erreichen, indem als Vorverarbeitung die Punkte sortiert werden und danach eine binäre Suche nach den Endpunkten des Intervalls vorgenommen wird, um alle Punkte zurückzugeben, die dazwischen liegen. Eine andere Lösung wäre, einen binären Suchbaum zu konstruieren und dann eine einfache rekursive Traversierung des Baumes zu realisieren, wobei innerhalb des Intervalls liegende Punkte zurückgegeben und außerhalb des Intervalls befindliche Teile des Baumes ignoriert werden. Das benötigte Programm ist eine einfache rekursive Traversierung des Baumes (siehe Kapitel 4). Falls sich der linke Endpunkt des Intervalls links von dem Punkt an der Wurzel befindet, durchsuchen wir (rekursiv) den linken Teilbaum und analog den rechten, wobei wir jeden Knoten, den wir vorfinden, prüfen, um festzustellen, ob sein Punkt im Intervall liegt:

    type interval = record x1,x2: integer end;
    procedure treerange(t: link; int: interval);
      var tx1,tx2: boolean;
      begin
      if t<>z then
        begin
        tx1:=t^.key>=int.x1;
        tx2:=t^.key<=int.x2;
        if tx1 then treerange(t^.l,int);
        if tx1 and tx2
          then {t^.key is within the range}
        if tx2 then treerange(t^.r,int);
        end
      end;

Die Effizienz dieses Programms könnte noch etwas erhöht werden, wenn das Intervall int als eine globale Variable verwendet würde, anstatt seine unveränderten Werte bei jedem rekursiven Aufruf weiterzureichen. Abbildung 26.1 zeigt die gefundenen Punkte, wenn dieses Programm für einen exemplarischen Baum abgearbeitet wird. Beachten Sie, daß die zurückgegebenen Punkte in dem Baum nicht verbunden sein müssen.

Abbildung 26.1
Abbildung 26.1 Bereichssuche (eindimensional) mit einem binären Suchbaum.

Eigenschaft 26.1 Eindimensionale Bereichssuche kann mit O(N log N) Schritten für die Vorverarbeitung und O(R + log N) Schritten für die Bereichssuche ausgeführt werden, wobei R die Anzahl der Punkte ist, die tatsächlich in dem Bereich liegen.

Dies folgt unmittelbar aus elementaren Eigenschaften der Suchstrukturen (siehe Kapitel 14 und 15). Bei Bedarf könnte ein ausgeglichener Baum verwendet werden. w.z.b.w.

Unser Ziel in diesem Kapitel besteht darin, die gleichen Laufzeiten für die mehrdimensionale Bereichssuche zu erreichen. Der Parameter R kann sehr groß sein: Wenn die Möglichkeit gegeben ist, Bereiche betreffende Anfragen beantworten zu lassen, könnte ein Anwender leicht Anfragen formulieren, die alle oder beinahe alle Punkte betreffen. Das Auftreten dieses Typs von Anfragen muß sicher in vielen Anwendungen erwartet werden, doch sind keine ausgeklügelten Algorithmen erforderlich, wenn alle Anfragen von diesem Typ sind. Die von uns betrachteten Algorithmen werden mit dem Ziel entwickelt, für Anfragen effizient zu sein, bei denen nicht zu erwarten ist, daß eine große Anzahl von Punkten zurückzugeben ist.


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