Robert Sedgewick: Algorithmen

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


26. Bereichssuche



Zweidimensionale Bäume

Zweidimensionale (2D-) Bäume sind dynamische, anpaßbare Datenstrukturen, die binären Bäumen sehr ähnlich sind, jedoch einen geometrischen Raum in einer Weise aufteilen, die für die Anwendung bei der Bereichssuche und anderen Problemen zweckmäßig ist. Die Idee besteht darin, binäre Suchbäume mit Punkten in den Knoten zu erzeugen und dabei die Koordinaten y und x der Punkte in alternierender Folge als Schlüssel zu verwenden.

Zum Einfügen von Punkten in 2D-Bäume wird der gleiche Algorithmus verwendet wie bei normalen binären Suchbäumen, nur daß wir an der Wurzel die y-Koordinate verwenden (gehe nach links, wenn der einzufügende Punkt eine kleinere y-Koordinate hat als der Punkt an der Wurzel, andernfalls gehe nach rechts), wir danach auf der nächsten Ebene die x-Koordinate verwenden, dann auf der folgenden Ebene die y-Koordinate usw., bis ein äußerer Knoten erreicht wird. Abbildung 26.4 zeigt den 2D-Baum, der unserer kleinen Punktmenge entspricht.

Abbildung 26.4
Abbildung 26.4 Ein zweidimensionaler (2D-) Baum.

Die Bedeutung dieses Verfahrens besteht darin, daß es einer Aufteilung der Ebene in einer einfachen Weise entspricht: Alle Punkte, die sich unterhalb des Punktes an der Wurzel befinden, kommen in den linken Teilbaum, alle, die sich oberhalb von ihm befinden, in den rechten Teilbaum; danach kommen alle Punkte, die oberhalb des Punktes an der Wurzel und links von dem Punkt im rechten Teilbaum liegen, in den linken Teilbaum des rechten Teilbaumes der Wurzel usw.

Abbildung 26.5
Abbildung 26.5 Zerlegung der Ebene mittels eines 2D-Baumes: Anfangsschritte.

Die Abbildungen 26.5 und 26.6 zeigen, wie die Ebene entsprechend der Konstruktion des Baumes aus Abbildung 26.4 aufgeteilt wird. Zuerst wird auf der Höhe der y-Koordinate von A, des ersten eingefügten Knotens, eine horizontale Linie gezeichnet. Danach wird B, da es sich unterhalb von A befindet, links von A in den Baum aufgenommen, und die Halbebene unterhalb von A wird mittels einer vertikalen Linie bei der x-Koordinate von B zerlegt (zweite Skizze in Abbildung 26.5). Danach gehen wir, da sich C unterhalb von A befindet, an der Wurzel nach links, und da es sich links von B befindet, in B nach links und zerlegen den Teil der Ebene, der sich unterhalb von A und links von B befindet, mittels einer horizontalen Linie bei der y-Koordinate von C (dritte Skizze in Abbildung 26.5). Das Einfügen von D ist ähnlich, doch dann wird E rechts von A in den Baum aufgenommen, da es sich oberhalb von A befindet (erste Skizze in Abbildung 26.6) usw.

Abbildung 26.6
Abbildung 26.6 Zerlegung der Ebene mittels eines 2D-Baumes: Fortsetzung.

Jeder äußere Knoten des Baumes entspricht einem bestimmten Rechteck in der Ebene. Jedes Gebiet entspricht einem äußeren Knoten im Baum; jeder Punkt liegt auf einem horizontalen oder vertikalen Geradenabschnitt, der die Zerlegung definiert, die bei diesem Punkt im Baum vorgenommen wurde.

Das Programm für die Konstruktion von 2D-Bäumen ist eine einfache Modifikation der gewöhnlichen Suche mit Hilfe binärer Bäume in der Weise, daß auf jeder Ebene zwischen den x- und y-Koordinaten gewechselt wird.

    type link^=node;
         node=record p: point; l,r: link end;
    var  t,head,z: link;
    procedure treeinsert(p: point; t: link);
      var f: link;
          d,td: boolean;
      begin
      d:=true;
      repeat
        if d then td:=p.x<t^.p.x
          else td:=p.y<t^.p.y;
        f:=t;
        if td then t:=t^.l else t:=t^.r;
        d:=not d;
      until t=z;
      new(t); t^.p:=p; t^.l:=z; t^.r:=z;
      if td then f^.l:=t else f^.r:=t;
      end;

Wie üblich benutzen wir einen Kopfknoten head mit einem künstlichen Punkt (0,0), der »kleiner« ist als alle anderen Punkte, so daß der Baum am rechten Ast von head hängt. Ein künstlicher Knoten z wird verwendet, um alle äußeren Knoten darzustellen. Der Aufruf treeinsert(p,head) bewirkt das Einfügen eines neuen p enthaltenden Knotens in den Baum. Eine boolesche Variable d wechselt auf dem Weg im Baum abwärts jedesmal ihren Wert, um die abwechselnden Tests für die x- und y-Koordinaten auszuführen. Ansonsten ist die Prozedur mit der Standardprozedur aus Kapitel 14 identisch.

Eigenschaft 26.3 Die Konstruktion eines 2D-Baumes aus N zufälligen Punkten erfordert im durchschnittlichen Fall 2N ln N Vergleiche.

Tatsächlich haben 2D-Bäume für zufällig verteilte Punkte die gleichen Leistungsfähigkeitsmerkmale wie binäre Suchbäume. Beide Koordinaten spielen die Rolle zufälliger »Schlüssel«. w.z.b.w.

Um eine Bereichssuche unter Benutzung von 2D-Bäumen auszuführen, erzeugen wir in der Vorverarbeitungsphase zuerst den 2D-Baum aus den Punkten:

    procedure preprocess;
      function initialize: link;
        var t: link;
        begin
        p[0].x:=0; p[0].y:=0; p[0].info:=0;
        new(t); t^.p:=p[0]; t^.r:=z;
        initialize:=t
        end;
      begin
      new(z); head:=initialize;
      for i:=1 to N do treeinsert(p[i],head);
      end;

Abbildung 26.7
Abbildung 26.7 Bereichssuche in einem 2D-Baum.

Für die Bereichssuche vergleichen wir dann den Punkt bei jedem Knoten mit dem Bereich längs der Dimension, die benutzt wurde, um die Ebene dieses Knotens zu zerlegen. In unserem Beispiel beginnen wir, indem wir sowohl bei der Wurzel als auch bei dem Knoten E nach rechts gehen, da sich unser Suchrechteck vollständig oberhalb von A und rechts von E befindet. Danach müssen wir uns beim Knoten F in beiden Teilbäumen abwärts bewegen, da F in dem durch das Rechteck definierten x-Bereich liegt (beachten Sie, daß dies nicht das gleiche ist, wie wenn wir sagen würden, daß F im Rechteck liegt). Dann werden die linken Teilbäume von P und K geprüft, was der Prüfung der Gebiete der Ebene entspricht, die sich mit dem Suchrechteck überschneiden. (Siehe Abbildungen 26.7 und 26.8.)

Abbildung 26.8
Abbildung 26.8 Bereichssuche in einem 2D-Baum (Zerlegung der Ebene).

Dieser Prozeß läßt sich mittels einer einfachen Verallgemeinerung der zu Beginn dieses Kapitels betrachteten eindimensionalen Prozedur treerange leicht implementieren:

    procedure range(t: link; rect: rectangle; d: boolean);
      var t1,t2,tx1,tx2,ty1,ty2: boolean;
      begin
      if t<>z then
        begin
        tx1:=rect.x1<t^.p.x; tx2:=t^.p.x<=rect.x2;
        ty1:=rect.y1<t^.p.y; tx2:=t^.p.y<=rect.y2;
        if d then begin t1:=tx1; t2:=tx2 end
          else begin t1:=ty1; t2:=ty2 end;
        if t1 then range(t^.l,rect, not d);
        if insiderect(t^.p, rect) 
          then {point t^.p is within the range}
        if t2 then range(t^.r,rect, not d);
        end
      end;

Bei dieser Prozedur wird nur dann in beiden Teilbäumen abwärts gegangen, wenn die zerlegende Linie das Rechteck schneidet, was bei relativ kleinen Rechtecken nicht oft vorkommen dürfte. Abbildung 26.8 zeigt die Zerlegungen der Ebene und die untersuchten Punkte für unsere beiden Beispiele.

Eigenschaft 26.4 Für die Bereichssuche mit einem 2D-Baum scheinen ungefähr R + log N Schritte erforderlich zu sein, um in einem N Punkte enthaltenden Gebiet R Punkte in sinnvollen Bereichen zu finden.

Abbildung 26.9
Abbildung 26.9 Bereichssuche in einem umfangreichen 2D-Baum.

Dieses Verfahren wurde noch nicht umfassend analysiert, und die angegebene Eigenschaft ist eine Vermutung, die ausschließlich auf empirischen Untersuchungen beruht. Natürlich hängt die Leistungsfähigkeit (und die Analyse) immer sehr stark von dem verwendeten Bereichstyp ab. Doch das Verfahren hält einem Vergleich mit dem Gitterverfahren sehr gut stand und ist etwas weniger von der »Zufälligkeit« in der Punktmenge abhängig. Abbildung 26.9 zeigt den 2D-Baum für unser umfangreiches Beispiel. w.z.b.w.


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