K-Dimensional Tree in C++
An effective data structure for arranging and searching multidimensional data is a k-dimensional tree, sometimes known as a k-d tree. Applications such as range search in k-dimensional spaces and nearest neighbour search in computer science and computational geometry benefit greatly from it. K-d trees are a unique kind of binary tree to effectively divide and arrange data points to enable speedy data retrieval and searching in multi-dimensional space. Each node in a k-d tree is connected to a splitting hyper plane and represents a k-dimensional point. The k-dimensional space is split into two half-spaces by this hyper plane, with each side's points being bigger or less than the hyper plane in a given dimension. As we down the tree, the splitting size option changes.
For instance, it could be divided along the x-axis at the root, the y-axis at the following level, and further down.
Applications for K-d trees include quickly determining a point's closest neighbours and conducting range searches in k-dimensional space to locate all points within a certain distance of a query point. They are particularly helpful for optimizing search queries and working with enormous datasets. A class-based data structure can be used to create a k-d tree in C++. This class should provide methods for creating and balancing the tree, as well as inserting and searching point’s. The particular needs of your application may influence the choice of how to implement a k-d tree.
Methods for K-Dimensional Tree in C++:
- Insertion Method:
Insert (const Point& point): This technique adds a new point to the k-d tree while preserving its structural integrity. At each level of the tree, it entails recursively splitting the space along several dimensions.
- Methods of Searching:
findNearestNeighbour (const Point& query): This function looks up the closest neighbour in the k-d tree to the specified query point. It entails going over the tree, taking into account various splitting dimensions, and updating the nearest neighbour when necessary.
rangeSearch(const Point& query, double radius): Use this function to execute a range search that locates all points that are within a given radius (or range) of the query point.
- Methods for Balancing and Construction (Optional):
constructTree(std::vector<Point> points): This function takes a list of points as input and builds a k-d tree. It may include using methods like median-based splitting to ensure a balanced tree.
balanceTree(): A technique for k-d tree balancing, which is critical for search operation optimization.
- Additional Useful methods:
The distance between two points in k-dimensional space can be determined using the formula distance (const Point& p1, const Point& p2). This approach is commonly used in the nearest neighbour search.
->Numerous assistive techniques for node construction, tree traversal, and other tree upkeep activities.
Example:
Let's take an example to illustrate the K-Dimensional tree in C++:
#include <iostream> #include <vector> #include <cmath> struct Point { std::vector<double> coordinates; }; struct Node { Point point; Node* left; Node* right; }; class KDTree { public: KDTree() : root(nullptr) {} void insert(const Point& point) { root = insertRecursive(root, point, 0); } Point findNearestNeighbor(const Point& query) { nearestNeighbor = root->point; nearestNeighborDist = distance(root->point, query); findNearestNeighborRecursive(root, query, 0); return nearestNeighbor; } private: Node* root; Point nearestNeighbor; double nearestNeighborDist; Node* insertRecursive(Node* node, const Point& point, int depth) { if (node == nullptr) { Node* newNode = new Node(); newNode->point = point; return newNode; } int k = point.coordinates.size(); int dim = depth % k; if (point.coordinates[dim] < node->point.coordinates[dim]) { node->left = insertRecursive(node->left, point, depth + 1); } else { node->right = insertRecursive(node->right, point, depth + 1); } return node; } void findNearestNeighborRecursive(Node* node, const Point& query, int depth) { if (node == nullptr) return; double dist = distance(node->point, query); if (dist < nearestNeighborDist) { nearestNeighborDist = dist; nearestNeighbor = node->point; } int k = query.coordinates.size(); int dim = depth % k; if (query.coordinates[dim] < node->point.coordinates[dim]) { findNearestNeighborRecursive(node->left, query, depth + 1); if(query.coordinates[dim]+nearestNeighborDist>= node->point.coordinates[dim]) { findNearestNeighborRecursive(node->right, query, depth + 1); } } else { findNearestNeighborRecursive(node->right, query, depth + 1); if(query.coordinates[dim]-nearestNeighborDist <= node->point.coordinates[dim]) { findNearestNeighborRecursive(node->left, query, depth + 1); } } } double distance(const Point& p1, const Point& p2) { double dist = 0; for (int i = 0; i < p1.coordinates.size(); ++i) { dist += std::pow(p1.coordinates[i] - p2.coordinates[i], 2); } return std::sqrt(dist); } }; int main() { KDTree tree; Point p1{{2, 3}}; Point p2{{5, 4}}; Point p3{{9, 6}}; Point p4{{4, 7}}; Point p5{{8, 1}}; tree.insert(p1); tree.insert(p2); tree.insert(p3); tree.insert(p4); tree.insert(p5); Point query{{7, 5}}; Point nearest = tree.findNearestNeighbor(query); std::cout<<"NearestNeighbor:("<<nearest.coordinates[0]<<","<<nearest.coordinates[1] << ")" << std::endl; return 0; }
Output:
Nearest Neighbor: (5, 4)
In this example, the output displays "Nearest Neighbour: (5, 4)" when the query point {7, 5} is discovered to have a nearest neighbour of {5, 4}.
Conclusion:
The provided code gives a basic C++ implementation of a k-d tree. Primarily focused on closest neighbour searches, the k-d tree is a flexible data structure that performs exceptionally well in organizing and searching multimedia data. This code outlines key methods for inserting points and locating the nearest neighbour, together with the Point and Node structures and the KDTree class. The insertion technique achieves tree balance by switching up the splitting dimensions and guarantees an effective structure. Utilizing the query point and the splitting dimension as inputs, the nearest neighbour search algorithm repeatedly explores the tree and updates the nearest neighbour. By adding new features and improving efficiency as needed, this code can be used as a great foundation for developing more complex k-d tree applications, such as range and nearest neighbour searches.