Ein -dimensionaler Baum oder -d-Baum ist ein balancierter Suchbaum zur Speicherung von Punkten aus dem . 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 statt in (siehe Komplexitätstheorie - Landau-Notation).
k-d-Bäume sind Spezialfälle von BSP-Bäumen, deren teilende Hyperebenen entlang der Achsen des Koordinatensystems ausgerichtet sind.
Er wurde von Jon Bentley eingeführt.
Es gibt homogene und inhomogene k-d-Bäume. Bei homogenen k-d-Bäumen speichert jeder Knoten einen Datensatz. Bei der inhomogenen Variante enthalten die inneren Knoten lediglich Schlüssel, die Blätter enthalten Verweise auf Datensätze.
Bei einem inhomogenen k-d-Baum sei die achsenparallele -dimensionale Hyperebene an der Stelle . Für die Wurzel teilt man die Punkte durch die Hyperebene in zwei möglichst gleich große Punktemengen und trägt das in die Wurzel ein, links davon werden alle Punkte gespeichert, deren kleiner sind als , rechts von der Wurzel alle größeren. Für den linken Kindknoten werden die Punkte wiederum durch eine neue Splitebene geteilt und das in dem inneren Knoten gespeichert. Links davon werden alle Punkte gespeichert, deren kleiner als 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.
Weil es viele Möglichkeiten gibt, an den Koordinatenachsen ausgerichtete Hyperebenen zu wählen, gibt es viele verschiedene Möglichkeiten, k-d-Bäume zu erstellen. Die übliche Methode, einen k-d-Baum zu konstruieren, hat folgende Einschränkungen:
Dieses Verfahren führt zu einem balancierten k-d-Baum, in dem jeder Blattknoten ungefähr den gleichen Abstand vom Wurzelknoten hat. Balancierte Bäume sind jedoch nicht notwendigerweise für alle Anwendungen optimal. Es ist nicht unbedingt erforderlich, jeweils den Median der Punkte auszuwählen. Wenn nicht der Median der Punkte ausgewählt wird, gibt es keine Garantie, dass der Baum balanciert ist. Um zu vermeiden, dass alle Punkte sortiert werden müssen, z. B. mit Heapsort oder Mergesort, ist es sinnvoll, eine feste Anzahl von zufällig ausgewählten Punkten zu sortieren (siehe Zufallsgenerator) und den Median dieser Punkte zu verwenden. In der Praxis führt diese Methode oft zu balancierten Bäumen.
Ein k-d-Baum lässt sich in der Laufzeit konstruieren. Orthogonale Bereichsanfragen lassen sich in beantworten, wobei die Größe der Antwort bezeichnet. Der Speicherplatzbedarf für den Baum selbst liegt in .
Die Abbildung rechts zeigt einen Teil der zweidimensionalen Ebene mit 6 gegebenen Punkten. Jeder dieser Punkte definiert eine Gerade (eindimensionale Hyperebene), sodass die zweidimensionale Ebene in 7 Gebiete (Punktemenge) aufgeteilt wird. Die Abbildung darunter zeigt den sich daraus ergebenden 2-d-Baum mit 6 Knoten. Der Wurzelknoten teilt die Ebene nach der x-Koordinate, die „Kinder“ nach der y-Koordinate und „Enkel“ wieder nach der x-Koordinate.
Die Hauptfunktion für das Erzeugen eines k-d-Baums hat 2 rekursive Aufrufe - einen für den linken und einen für den rechten Teilbaum. Sie kann in Pseudocode wie 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 den Wurzelknoten des Baums oder Teilbaums. Das Attribut knoten.punkt ist ein Zeiger auf den Punkt, der dem Wurzelknoten zugeordnet ist. Die Attribute knoten.links und knoten.rechts sind Zeiger auf den Wurzelknoten des linken bzw. rechten Teilbaums.
Das folgende Beispiel in der Programmiersprache C++ zeigt eine Implementierung für die Erzeugung eines k-d-Baums. Der oben beschriebene Algorithmus ist in der Funktion createTree implementiert. Diese Funktion und der Datentyp node für die Knoten des Baums ist in der Klasse KDTree deklariert. Bei der Ausführung des Programms wird die Funktion main verwendet, die den Punkt mit dem kürzesten Abstand zu einem gegebenen Punkt und die Anzahl der besuchten Knoten auf der Konsole ausgibt. Dabei wird das Beispiel oben mit den Punkten in 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 Funktion 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 dem 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
}
|