Kartesischer Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Eine Folge von Zahlen und der daraus abgeleitete Kartesische Baum.

Ein kartesischer Baum ist ein aus einer Folge von Zahlen abgeleiteter Binärheap, mit der zusätzlichen Eigenschaft, dass ein in-order-Durchlauf wieder die ursprüngliche Folge liefert. Der kartesische Baum für eine Folge kann in Linearzeit konstruiert werden.

Definition[Bearbeiten | Quelltext bearbeiten]

Der kartesische Baum einer Folge von total geordneten Elementen ist wie folgt definiert:

  1. Der kartesische Baum ist ein Binärbaum.
  2. Für jedes Element der Folge existiert genau ein Knoten im Baum.
  3. Ein in-order-Durchlauf des Baumes liefert die ursprüngliche Folge. Das heißt: der linke Teilbaum der Wurzel besteht aus den Elementen, die in der Folge vor dem Wurzelelement stehen, der rechte Teilbaum aus den Elementen danach; dies gilt für jeden Teilbaum.
  4. Der Baum erfüllt die Heap-Eigenschaft (im Folgenden immer min-Heap).

Gemäß der Heap-Eigenschaft ist das Wurzelelement das kleinste Element der Folge. Dadurch lässt sich der Baum auch rekursiv definieren: Die Wurzel ist der minimale Wert der Folge und der linke und rechte Teilbaum sind die kartesischen Bäume der Teilfolgen links und rechts der Wurzel.

Falls die Elemente der Folge nicht paarweise verschieden sind, ist deren kartesischer Baum nicht eindeutig bestimmt. Die Eindeutigkeit lässt sich durch Wahl einer deterministischen Tie-Break-Regel gewährleisten (beispielsweise: "Betrachte das erste Vorkommen zweier gleicher Elemente als das kleinere").

Konstruktion[Bearbeiten | Quelltext bearbeiten]

Aus der rekursiven Definition ergibt sich bereits ein naives Konstruktionsverfahren mit Worst-Case-Laufzeit . Die Konstruktion eines kartesischen Baums einer gegebenen Folge ist jedoch in Linearzeit möglich. Dazu wird von links nach rechts über die Folge der Elemente iteriert, sodass zu jedem Zeitpunkt (d.h. in Iteration ) bereits der kartesische Baum der ersten Elemente vorhanden ist. Um in der nächsten Iteration das nächste Element hinzuzufügen, beginne bei dem Knoten, der dem vorherigen Element entspricht, und folge von dort dem Pfad zur Wurzel, bis der tiefste Knoten erreicht wird, dessen zugehöriges Element kleiner als ist. Der Knoten für wird nun als rechter Teilbaum an angehängt und der vormals rechte Teilbaum von wird stattdessen der linke Teilbaum des neu eingefügten Knotens zu . In dem Spezialfall, dass auf dem Pfad zur Wurzel (einschließlich) kein Element gefunden wird, das kleiner als ist, wird die Wurzel des neuen kartesischen Baumes. Dazu wird die alte Wurzel als linkes Kind angehängt.

Die Gesamtlaufzeit für die Konstruktion ist linear in der Anzahl der Folgenelemente, da die Zeit für die Suche nach dem Knoten gegen die Anzahl der Knoten aufgerechnet werden kann, die nach der Iteration nicht mehr auf dem rechtesten Pfad liegen, während die Operationen zum Einfügen des neuen Knotens und das Umhängen eines Teilbaums in konstanter Zeit möglich sind. [1]

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Range-Minimum-Query[Bearbeiten | Quelltext bearbeiten]

Eine Bereichsminimumsanfrage (RMQ) auf einer Folge sucht das minimale Element einer zusammenhängenden Teilfolge. Im kartesischen Baum findet sich das Minimum der Teilfolge im tiefsten gemeinsamen Vorfahren (Lowest Common Ancestor) des ersten und des letzten Knotens der Teilfolge. In der oben verwendeten Beispielfolge findet sich zum Beispiel für die Teilfolge das Minimum im Lowest Common Ancestor des ersten und letzten Elements ( und ).

Da der Lowest Common Ancestor unter Verwendung einer Datenstruktur mit linearem Speicherplatz in linearer Zeit ermittelt werden kann[2][3], lassen sich mit Hilfe eines kartesischen Baumes auch RMQs innerhalb dieser Schranken beantworten.

3-seitige Bereichsanfragen[Bearbeiten | Quelltext bearbeiten]

Der Name des kartesischen Baumes stammt von der Verwendung zur Beantwortung dreiseitiger Bereichsanfragen in der kartesischen Ebene. Gesucht sind alle Punkte die die Bedingungen (1) und (2) erfüllen. Dazu werden die Punkte zunächst nach x-Koordinate sortiert und der kartesische Baum mit Heap-Eigenschaft bezüglich der y-Koordinate konstruiert. Für eine konkrete Anfrage bilden nun die Punkte, die Bedingung (1) erfüllen, eine zusammenhängende Teilfolge, wobei der erste Knoten der Teilfolge (mit kleinster x-Koordinate) und der letzte (mit größter x-Koordinate) sei. Im Lowest Common Ancestor von und findet sich der Punkt aus diesem Intervall mit minimaler y-Koordinate. Falls die y-Koordinate von kleiner als die Schranke ist, ( liegt also im gesuchten Bereich) wird ausgegeben und rekursiv auf den Teilfolgen zwischen und sowie zwischen und weitergesucht. Auf diese Weise lassen sich, nachdem einmalig die Knoten und bestimmt wurden (z.B. mit binärer Suche), alle Punkte innerhalb des gesuchten Bereichs in konstanter Zeit pro Punkt ermitteln[1].

Geschichte[Bearbeiten | Quelltext bearbeiten]

Kartesische Bäume gehen zurück auf Vuillemin (1980)[4], der einen Spezialfall der oben beschriebenen kartesischen Bäume für eine Folge von Punkten im kartesischen Koordinatensystem beschrieb: Dabei bezieht sich die Heap-Eigenschaft auf die y-Koordinate der Punkte, ein in-order-Durchlauf liefert die sortierte Folge der x-Koordinaten. Gabow, Bentley, und Tarjan (1984)[1] und weitere Autoren folgten der hier gegebenen Definition, in der ein kartesischer Baum für beliebige Folgen definiert wird und abstrahierten damit von dem ursprünglichen geometrischen Problem.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b c Gabow, H.N., J.L. Bentley, and R.E. Tarjan: Scaling and related techniques for geometry problems. In: Proceedings of the sixteenth annual ACM symposium on Theory of computing. 1984, S. 135-143. doi:10.1145/800057.808675.
  2. Baruch Schieber, Uzi Vishkin: On finding lowest common ancestors: simplification and parallelization. In: SIAM Journal on Computing. 17, Nr. 6, 1988, S. 1253–1262. doi:10.1137/0217079.
  3. Dov Harel, Robert E. Tarjan: Fast algorithms for finding nearest common ancestors. In: SIAM Journal on Computing. 13, Nr. 2, 1984, S. 338–355. doi:10.1137/0213024.
  4. Jean Vuillemin: A unifying look at data structures. In: ACM (Hrsg.): Commun. ACM. 23, Nr. 4, New York, NY, USA, 1980, S. 229–239. doi:10.1145/358841.358852.