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.

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.

#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

Geschichte

Kartesische Bäume gehen zurück auf Vuillemin (1980), 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) 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. 1 2 3 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.