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.

Eine Folge von Zahlen und der daraus abgeleitete Kartesische Baum.

Definition

Bearbeiten

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

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]

Programmierung

Bearbeiten

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

Bearbeiten

Range-Minimum-Query

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[3][4], lassen sich mit Hilfe eines kartesischen Baumes auch RMQs innerhalb dieser Schranken beantworten.

3-seitige Bereichsanfragen

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

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

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. 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.