k-d-Baum

Ein ${\displaystyle k}$-dimensionaler Baum oder ${\displaystyle k}$-d-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem ${\displaystyle \mathbb {R} ^{k}}$. Er bietet ähnlich dem Bereichsbaum die Möglichkeit, orthogonale Bereichsanfragen durchzuführen. Die Anfragekomplexität ist zwar höher, dafür liegt der Speicheraufwand in ${\displaystyle O(k\cdot n)}$ statt in ${\displaystyle O(n\cdot (\log(n))^{k-1})}$ (siehe Komplexitätstheorie - Landau-Notation).

k-d-Bäume s​ind Spezialfälle v​on BSP-Bäumen, d​eren teilende Hyperebenen entlang d​er Achsen d​es Koordinatensystems ausgerichtet sind.

Er w​urde von Jon Bentley eingeführt.

Definition

Es g​ibt homogene u​nd inhomogene k-d-Bäume. Bei homogenen k-d-Bäumen speichert j​eder Knoten e​inen Datensatz. Bei d​er inhomogenen Variante enthalten d​ie inneren Knoten lediglich Schlüssel, d​ie Blätter enthalten Verweise a​uf Datensätze.

Bei einem inhomogenen k-d-Baum sei ${\displaystyle H_{i}(t)=(x_{1},x_{2},\ldots ,x_{i-1},t,x_{i+1},\ldots ,x_{k})}$ ${\displaystyle 1\leq i\leq k}$ die achsenparallele ${\displaystyle (k-1)}$-dimensionale Hyperebene an der Stelle ${\displaystyle t}$. Für die Wurzel teilt man die Punkte durch die Hyperebene ${\displaystyle H_{1}(t)}$ in zwei möglichst gleich große Punktemengen und trägt das ${\displaystyle t}$ in die Wurzel ein, links davon werden alle Punkte gespeichert, deren ${\displaystyle x_{1}}$ kleiner sind als ${\displaystyle t}$, rechts von der Wurzel alle größeren. Für den linken Kindknoten werden die Punkte wiederum durch eine neue Splitebene ${\displaystyle H_{2}(t)}$ geteilt und das ${\displaystyle t}$ in dem inneren Knoten gespeichert. Links davon werden alle Punkte gespeichert, deren ${\displaystyle x_{2}}$ kleiner als ${\displaystyle t}$ ist. Dies wird nun rekursiv über alle Dimensionen fortgeführt. Danach wird wieder bei der ersten Dimension angefangen, bis jeder Punkt durch Hyperebenen eindeutig identifiziert werden kann.

Algorithmus

Weil e​s viele Möglichkeiten gibt, a​n den Koordinatenachsen ausgerichtete Hyperebenen z​u wählen, g​ibt es v​iele verschiedene Möglichkeiten, k-d-Bäume z​u erstellen. Die übliche Methode, e​inen k-d-Baum z​u konstruieren, h​at folgende Einschränkungen:

• Wenn man sich im Baum nach unten bewegt, durchläuft man die Koordinatenachsen in einer bestimmten sich wiederholenden Reihenfolge, die zum Auswählen der Hyperebenen verwendet werden. Zum Beispiel definiert in einem 3-dimensionalen Baum der Wurzelknoten eine Ebene orthogonal zur x-Achse, die 2 "Kinder" des Wurzelknotens definieren 2 Ebenen orthogonal zur y-Achse, die "Enkel" orthogonal zur z-Achse, die "Urenkel" wieder orthogonal zur x-Achse usw.
• Knoten mit Punkten im k-dimensionalen Raum werden in den Baum eingefügt, indem jeweils der Median der Punkte in Bezug auf die aktuelle Koordinate ausgewählt wird, der die teilende Hyperebene definiert, und der neue Knoten abhängig von der Koordinate des Punkts in den linken oder rechten Teilbaum eingefügt wird. Die Punkte werden von unten nach oben in den Baum eingefügt.

Dieses Verfahren führt z​u einem balancierten k-d-Baum, i​n dem j​eder Blattknoten ungefähr d​en gleichen Abstand v​om Wurzelknoten ist. Balancierte Bäume s​ind jedoch n​icht notwendigerweise für a​lle Anwendungen optimal. Es n​icht unbedingt erforderlich ist, jeweils d​en Median d​er Punkte auszuwählen. Wenn n​icht der Median d​er Punkte ausgewählt wird, g​ibt es k​eine Garantie, d​ass der Baum balanciert ist. Um z​u vermeiden, d​ass alle Punkte sortiert werden müssen, z. B. m​it Heapsort o​der Mergesort, i​st es sinnvoll, e​ine feste Anzahl v​on zufällig ausgewählten Punkten z​u sortieren (siehe Zufallsgenerator) u​nd den Median dieser Punkte z​u verwenden. In d​er Praxis führt d​iese Methode o​ft zu balancierten Bäumen.

Ein k-d-Baum lässt sich in der Laufzeit ${\displaystyle O(n\cdot (k+\log(n)))}$ konstruieren. Orthogonale Bereichsanfragen lassen sich in ${\displaystyle O(n^{1-{\frac {1}{k}}}+a)}$ beantworten, wobei ${\displaystyle a}$ die Größe der Antwort bezeichnet. Der Speicherplatzbedarf für den Baum selbst liegt in ${\displaystyle O(k\cdot n)}$.

Beispiel für einen 2-d-Baum

Die Abbildung rechts z​eigt einen Teil d​er zweidimensionalen Ebene m​it 6 gegebenen Punkten. Jeder dieser Punkte definiert e​ine Gerade (eindimensionale Hyperebene), sodass d​ie zweidimensionale Ebene i​n 7 Gebiete (Punktemenge) aufgeteilt wird. Die Abbildung darunter z​eigt den s​ich daraus ergebenden 2-d-Baum m​it 6 Knoten. Der Wurzelknoten t​eilt die Ebene n​ach der x-Koordinate, d​ie "Kinder" n​ach der y-Koordinate u​nd "Enkel" wieder n​ach der x-Koordinate.

Pseudocode

Die Hauptfunktion für d​as Erzeugen e​ines k-d-Baums h​at 2 rekursive Aufrufe - e​inen für d​en linken u​nd einen für d​en rechten Teilbaum. Sie k​ann in Pseudocode w​ie folgt notiert werden:

Funktion kdTree(<Liste> punkteListe, int tiefe)
{
    // Index für die Koordinate aus der Aufruftiefe der Funktion berechnen
    // Die Division mit Rest stellt sicher, dass die gültigen Werte von 0 bis k - 1 durchlaufen werden
    int i := tiefe mod k

    // punkteListe sortieren und median als Pivotelement auswählen
    mediann:= Median in Bezug auf Koordinate i von punkteListe

    // Knoten und Teilbäume erzeugen
    Objekt knoten erzeugen
    // Median von punkteListe dem Wurzelknoten des Baums (oder Teilbaums) zuordnen
    knoten.punktk:= median
    // Rekursive Aufrufe
    knoten.linkss:= kdTree(Punkte in punkteListe vor median, tiefe + 1) // Linker Teilbaum
    knoten.rechtst:= kdTree(Punkte in punkteListe nach median, tiefe + 1) // Rechter Teilbaum
    // Knoten mit dem Median zurückgeben
    return knoten
}

Die Variable knoten enthält d​en Wurzelknoten d​es Baums o​der Teilbaums. Das Attribut knoten.punkt i​st ein Zeiger a​uf den Punkt, d​er dem Wurzelknoten zugeordnet ist. Die Attribute knoten.links u​nd knoten.rechts s​ind Zeiger a​uf den Wurzelknoten d​es linken bzw. rechten Teilbaums.

Programmierung

Das folgende Beispiel i​n der Programmiersprache C++ z​eigt eine Implementierung für d​ie Erzeugung e​ines k-d-Baums. Der o​ben beschriebene Algorithmus i​st in d​er Funktion createTree implementiert. Diese Funktion u​nd der Datentyp node für d​ie Knoten d​es Baums i​st in d​er Klasse KDTree deklariert. Bei d​er Ausführung d​es Programms w​ird die Funktion main verwendet, d​ie den Punkt m​it dem kürzesten Abstand z​u einem gegebenen Punkt u​nd die Anzahl d​er besuchten Knoten a​uf der Konsole ausgibt. Dabei w​ird das Beispiel o​ben mit d​en Punkten i​n der zweidimensionalen Ebene verwendet.[1][2]

Code-Schnipsel

#include <iostream> #include <array> #include <vector> #include <random> using namespace std; // Deklariert ein Template für den Typparameter des Arrays mit den Koordinaten template<typename coordinateType, int dimensions> // Deklariert eine Klasse für einen Punkt in einem mehrdimensionalen euklidischen Raum. Der Typparameter coordinateType muss ein numerischer Datentyp sein. class Point { public: // Konstruktor Point(initializer_list<coordinateType> list) { int length = min(dimensions, (int)list.size()); copy_n(list.begin(), length, coordinates.begin()); // Initialisiert das Array mit den Koordinaten } // Diese Funktion gibt die Koordinate der mit dem gegebenen Index zurück coordinateType get(int index) const { return coordinates[index]; } // Diese Funktion gibt den quadrierten Abstand des Punkts zum gegebenen Punkt zurück double getSquaredDistance(const Point& point) const { double squaredDistance = 0; for (int i = 0; i < dimensions; i++) { double difference = (double)get(i) - (double)point.get(i); squaredDistance += difference * difference; } return squaredDistance; } private: // Deklariert ein Array der Länge dimensions mit dem Typparameter coordinateType für die Koordinaten des Punkts array<coordinateType, dimensions> coordinates; }; template<typename coordinateType, int dimensions> // Deklariert den Operator <<, der die Koordinaten des gegebenen Punkts auf der Konsole ausgibt ostream& operator<<(ostream& output, const Point<coordinateType, dimensions>& point) { output << '('; for (int i = 0; i < dimensions; i++) { if (i > 0) { output << ", "; } output << point.get(i); } output << ')'; return output; } template<typename coordinateType, int dimensions> // Deklariert eine Klasse für den k-d-Baum class KDTree { public: typedef Point<coordinateType, dimensions> pointType; private: // Datentyp für die Knoten des Baums struct node { // Diese Funktion initialisiert den Knoten node(const pointType& _point) : point(_point), left(nullptr), right(nullptr) {} // Diese Funktion gibt die Koordinate mit dem gegebenen Index zurück coordinateType get(int index) const { return point.get(index); // Ruft die Funktions der Klasse Point auf } // Diese Funktion gibt den quadrierten Abstand zum gegebenen Punkt zurück double getSquaredDistance(const pointType& _point) const { return point.getSquaredDistance(_point); // Ruft die Funktions der Klasse Point auf } pointType point; // Punkt, der dem Knoten zugeordnet ist node* left; // Linker Nachfolger des Knoten node* right; // Rechter Nachfolger des Knoten }; node* root = nullptr; // Zeiger auf den Wurzelknoten des Baums node* nearestNode = nullptr; // Zeiger auf den bisher gefundenen Knoten mit dem kleinsten Abstand zum Wurzelknoten double smallestDistance = 0; // Abstand zum Wurzelknoten int numberOfVisited = 0; // Zähler für die bisher besuchten Knoten vector<node> nodes; // Vektor, der die Knoten des Baums enthält struct nodeCompare { // Vergleichsfunktion nodeCompare(int _index) : index(_index) {} // Deklariert den Operator (), der die Koordinaten mit dem gegebenen Index vergleicht. Gibt true zurück, wenn die Koordinate des ersten Knotens kleiner als die des zweiten Knotens ist, sonst false. bool operator()(const node& node1, const node& node2) const { return node1.point.get(index) < node2.point.get(index); } int index; }; // Diese rekursive Funktion erzeugt den Baum mit den Knoten im angegebenen Indexbereich und gibt einen Zeiger auf den Knoten mit dem Median der Punkte zurück node* createTree(int startIndex, int endIndex, int index) { // Abbruchbedingung für die Rekursion, gibt einen Nullzeiger zurück und verlässt die Funktion if (startIndex >= endIndex) { return nullptr; } int meanIndex = startIndex + (endIndex - startIndex) / 2; // Berechnet den mittleren Index auto i = nodes.begin(); // Iterator, der auf den ersten Knoten des Vektors zeigt // Setzt den richtigen Knoten auf den mittleren Index und teilt den Vektor nodes nach der Koordinaten mit dem Index in zwei Wertebereiche auf. Dafür wird die Vergleichsfunktion nodeCompare verwendet. nth_element(i + startIndex, i + meanIndex, i + endIndex, nodeCompare(index)); index = (index + 1) % dimensions; // Index für die Koordinate um 1 erhöhen, bei Überlauf auf 0 setzen nodes[meanIndex].left = createTree(startIndex, meanIndex, index); // Rekursiver Aufruf für den linken Teilbaum, weist den linken Nachfolgerknoten zu nodes[meanIndex].right = createTree(meanIndex + 1, endIndex, index); // Rekursiver Aufruf für den rechten Teilbaum, weist den rechten Nachfolgerknoten zu return &nodes[meanIndex]; // Gibt den Knoten mit dem mittleren Index zurück } // Diese rekursive Funktion bestimmt den Knoten des Baums, dessen Punkt den kleinsten Abstand vom gegebenen Punkt hat. Das Ergebnis wird Attributen von KDTree zugewiesen. void nearest(node* currentNode, const pointType& point, int index) { // Wenn der Zeiger für den aktuellen Knoten ein Nullzeiger ist, Funktion verlassen if (currentNode == nullptr) { return; } numberOfVisited++; // Zähler für die bisher besuchten Knoten um 1 erhöhen double squaredDistance = currentNode->getSquaredDistance(point); // Funktionsaufruf, bestimmt den quadrierten Abstand des Punkts if (nearestNode == nullptr || squaredDistance < smallestDistance) // Wenn das Attribut für den Knoten noch nicht zugewiesen oder der quadrierte Abstand des gefundenen Punkts kleiner als der bisherige Abstand ist { smallestDistance = squaredDistance; // Weist den quadrierten Abstand dem Attribut zu nearestNode = currentNode; // Weist den aktuellen Knoten dem Attribut zu } // Wenn der gefundene Punkt den Abstand 0 vom gegebenen Punkt hat, Funktion verlassen if (smallestDistance == 0) { return; } double difference = (double)currentNode->get(index) - (double)point.get(index); // Berechnet die Differenz zwischen der Koordinate des aktuellen und des gegebenen Knotens index = (index + 1) % dimensions; // Index für die Koordinate um 1 erhöhen, bei Überlauf auf 0 setzen nearest(difference > 0 ? currentNode->left : currentNode->right, point, index); // Rekursiver Aufruf für den Nachfolgerknoten mit Fallunterscheidung, Differenz positiv: linker Knoten, Differenz negativ: rechter Knoten // Wenn die Differenz der Koordinatenwerte größer ist als der bisher gefundene kleinste Abstand, Funktion verlassen if (difference * difference >= smallestDistance) { return; } nearest(difference > 0 ? currentNode->right : currentNode->left, point, index); // Rekursiver Aufruf für den Nachfolgerknoten mit Fallunterscheidung, Differenz positiv: rechter Knoten, Differenz negativ: linker Knoten } public: template<typename iterator> // Konstruktor, der die Punkte im gegebenen Bereich in den Baum einfügt KDTree(iterator iterator1, iterator iterator2) : nodes(iterator1, iterator2) { root = createTree(0, nodes.size(), 0); // Funktionsaufruf, weist den Zeiger auf den Wurzelknoten zu } // Gibt true zurück, wenn der Baum leer ist, sonst false bool empty() const { return nodes.empty(); } // Gibt die Anzahl der besuchten Knoten nach dem letzten Aufruf der Funktion nearest zurück int visited() const { return numberOfVisited; } // Gibt den Abstand zwischen dem gegebenen Punkt und dem zuletzt von der Funktion nearest zurückgegebenen Punkt zurück double distance() const { return sqrt(smallestDistance); } // Diese Funktion gibt den Punkt mit den kleinsten Abstand zum gegebenen Punkt zurück. Wenn der Baum leer ist, wird eine Ausnahme ausgelöst. pointType& nearest(const pointType& point) { // Wenn der Zeiger für den Wurzelknoten auf keinen Knoten verweist if (root == nullptr) { throw logic_error("Der Baum ist leer"); // Wirft eine Ausnahme } // Setzt die Startwerte der Variablen nearestNode = nullptr; numberOfVisited = 0; smallestDistance = 0; nearest(root, point, 0); // Funktionsaufruf return nearestNode->point; } }; // Hauptfunktion die das Programm ausführt int main() { // Typdefinitionen typedef Point<int, 2> point2d; typedef KDTree<int, 2> kdTree2d; // Deklariert und initialisiert ein Array mit 6 Punkten point2d points[] = { { 2, 3 }, { 5, 4 }, { 9, 6 }, { 4, 7 }, { 8, 1 }, { 7, 2 } }; // Deklariert und initialisiert die Variable für den k-d-Baum kdTree2d tree(begin(points), end(points)); point2d nearestPoint = tree.nearest({ 9, 2 }); // Funktionsaufruf, weist den Punkt mit dem kleinsten Abstand der Variablen zu cout << "Punkt mit dem kleinsten Abstand: " << nearestPoint << endl; // Ausgabe auf der Konsole cout << "Abstand: " << tree.distance() << endl; // Ausgabe auf der Konsole cout << "Anzahl der besuchten Knoten: " << tree.visited() << endl; // Ausgabe auf der Konsole }

Siehe auch

• Binary Space Partitioning
• Quadtree
• Octree
• UB-Baum
• R-Baum
• Bereichsbaum
• Gridfile

Literatur

• J. L. Bentley: Multidimensional binary search trees used for associative searching. In: Communications of the ACM, 18, 9, September 1975, S. 509–517.
• J. L. Bentley: K-d Trees for Semidynamic Point Sets. In: SCG ’90: Proceedings of the 6th Annual Symposium on Computational Geometry, 1990, S. 187–197, doi:10.1145/98524.98564.
• Rolf Klein: Algorithmische Geometrie, 2. Auflage. Springer-Verlag, Berlin/Heidelberg 2005, ISBN 3-540-20956-5.

Weblinks

• k-d-Baum. Universität Osnabrück

Einzelnachweise

1. Rosetta Code: K-d tree
2. GeeksforGeeks: K Dimensional Tree