Kartesischer Baum

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

Der kartesische Baum einer Folge von Elementen, für die es eine Totalordnung gibt, 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

Aus der rekursiven Definition ergibt sich bereits ein naives Konstruktionsverfahren mit Worst-Case-Laufzeit ${\displaystyle {\mathcal {O}}(n^{2})}$. 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 ${\displaystyle i}$) bereits der kartesische Baum der ersten ${\displaystyle i}$ Elemente vorhanden ist. Um in der nächsten Iteration das nächste Element ${\displaystyle a_{i+1}}$ hinzuzufügen, beginne bei dem Knoten, der dem vorherigen Element ${\displaystyle a_{i}}$ entspricht, und folge von dort dem Pfad zur Wurzel, bis der tiefste Knoten ${\displaystyle y}$ erreicht wird, dessen zugehöriges Element kleiner als ${\displaystyle a_{i+1}}$ ist. Der Knoten für ${\displaystyle a_{i+1}}$ wird nun als rechter Teilbaum an ${\displaystyle y}$ angehängt und der vormals rechte Teilbaum von ${\displaystyle y}$ wird stattdessen der linke Teilbaum des neu eingefügten Knotens zu ${\displaystyle a_{i+1}}$. In dem Spezialfall, dass auf dem Pfad zur Wurzel (einschließlich) kein Element gefunden wird, das kleiner als ${\displaystyle a_{i+1}}$ ist, wird ${\displaystyle a_{i+1}}$ 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 ${\displaystyle y}$ 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]

Programmierung

Das folgende Beispiel in der Programmiersprache C++ zeigt die Implementierung für das Erzeugen eines kartesische Baum. Die rekursive Funktion createCartesianTree erzeugt den Baum. Die einzelnen Knoten haben den Datentyp Node und jeweils einen linken und einen rechten Kindknoten vom Datentyp Node. In der Funktion main wird die in-order Reihenfolge des kartesischen Baums ausgegeben.^[2]

#include <iostream> #include <string> #include <list> using namespace std; // Deklariert den Datentyp für die Knoten des Graphen struct Node { int value; Node* left, * right, * parent; }; // Diese rekursive Funktion erzeugt den Teilbaum des kartesischen Baums für das Intervall zwischen den gegebenen Indexen und gibt einen Zeiger auf den Knoten zurück Node* createCartesianTree(int numbers[], int startIndex, int endIndex) { // Wenn der Startindex größer als der Endindex ist, wird ein Nullzeiger zurückgegeben if (startIndex > endIndex) { return 0; } // Bestimmt den kleinsten Wert und den zugehörigen Index int index = startIndex; int minimum = numbers[index]; for (int i = startIndex + 1; i <= endIndex; i++) { if (numbers[i] < minimum) { index = i; minimum = numbers[i]; } } // Erzeugt den Knoten und setzt den Wert für den gefundenen Index Node* node = new Node; node->value = minimum; Node* leftNode = createCartesianTree(numbers, startIndex, index - 1); // Rekursiver Aufruf für den linken Teilbaum node->left = leftNode; // Wenn linker Teilbaum nicht leer, aktuellen Knoten als Elternknoten des Kindknotens setzen if (leftNode != 0) { node->left->parent = node; } Node* rightNode = createCartesianTree(numbers, index + 1, endIndex); // Rekursiver Aufruf für den rechten Teilbaum node->right = rightNode; // Rechten Kindknoten setzen // Wenn rechter Teilbaum nicht leer, aktuellen Knoten als Elternknoten des Kindknotens setzen if (rightNode != 0) { node->right->parent = node; } return node; } // Gibt die in-order-Reihenfolge des Baums als Text zurück string inOrderToString(Node* node) { if (node == 0) { return ""; } string leftSubtreeString = inOrderToString(node->left); string rootString = to_string(node->value); string rightSubtreeString = inOrderToString(node->right); return "(" + leftSubtreeString + rootString + rightSubtreeString + ")"; } // Hauptfunktion die das Programm ausführt int main() { // Initialisiert und deklariert ein Array mit 11 Werten für die Knoten des kartesischen Baums int numbers[] = { 9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5 }; int length = sizeof(numbers) / sizeof(numbers[0]); Node* root = createCartesianTree(numbers, 0, length - 1); // Aufruf der Funktion, die den kartesischen Baum erzeugt cout << "In-order Reihenfolge:" << inOrderToString(root) << endl; // Aufruf der Funktion, die die in-order-Reihenfolge auf der Konsole ausgibt }

Anwendungen

Range-Minimum-Query

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 ${\displaystyle (12,10,20,15)}$ das Minimum ${\displaystyle (10)}$ im Lowest Common Ancestor des ersten und letzten Elements (${\displaystyle 12}$ und ${\displaystyle 15}$).

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

3-seitige Bereichsanfragen

Der Name des kartesischen Baumes stammt von der Verwendung zur Beantwortung dreiseitiger Bereichsanfragen in der kartesischen Ebene. Gesucht sind alle Punkte ${\displaystyle (x,y)\in \mathbb {R} ^{2}}$ die die Bedingungen ${\displaystyle L\leq x\leq R}$ (1) und ${\displaystyle y\leq T}$ (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 ${\displaystyle l}$ der erste Knoten der Teilfolge (mit kleinster x-Koordinate) und ${\displaystyle r}$ der letzte (mit größter x-Koordinate) sei. Im Lowest Common Ancestor ${\displaystyle b}$ von ${\displaystyle r}$ und ${\displaystyle l}$ findet sich der Punkt aus diesem Intervall mit minimaler y-Koordinate. Falls die y-Koordinate von ${\displaystyle b}$ kleiner als die Schranke ${\displaystyle T}$ ist, (${\displaystyle b}$ liegt also im gesuchten Bereich) wird ${\displaystyle b}$ ausgegeben und rekursiv auf den Teilfolgen zwischen ${\displaystyle l}$ und ${\displaystyle b}$ sowie zwischen ${\displaystyle b}$ und ${\displaystyle r}$ weitergesucht. Auf diese Weise lassen sich, nachdem einmalig die Knoten ${\displaystyle l}$ und ${\displaystyle r}$ bestimmt wurden (z. B. mit binärer Suche), alle Punkte innerhalb des gesuchten Bereichs in konstanter Zeit pro Punkt ermitteln^[1].

Geschichte

Kartesische Bäume gehen zurück auf Vuillemin (1980)^[5], 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

1. 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. GeeksforGeeks: Cartesian Tree
3. Baruch Schieber, Uzi Vishkin: On finding lowest common ancestors: simplification and parallelization. In: SIAM Journal on Computing. 17. Jahrgang, Nr. 6, 1988, S. 1253–1262, doi:10.1137/0217079. 
4. Dov Harel, Robert E. Tarjan: Fast algorithms for finding nearest common ancestors. In: SIAM Journal on Computing. 13. Jahrgang, Nr. 2, 1984, S. 338–355, doi:10.1137/0213024. 
5. Jean Vuillemin: A unifying look at data structures. In: Commun. ACM. 23. Jahrgang, Nr. 4. ACM, New York, NY, USA 1980, S. 229–239, doi:10.1145/358841.358852.