c++ KDTree
时间: 2024-06-13 16:05:48 浏览: 13
以下是一个简单的C++实现k-d tree的例子:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
vector<int> point;
Node* left;
Node* right;
Node(vector<int> p) : point(p), left(NULL), right(NULL) {}
};
class KDTree {
public:
Node* root;
KDTree() : root(NULL) {}
void insert(vector<int> point) {
root = insert(root, point, 0);
}
Node* insert(Node* node, vector<int> point, int depth) {
if (node == NULL) {
return new Node(point);
}
int k = point.size();
int cd = depth % k;
if (point[cd] < node->point[cd]) {
node->left = insert(node->left, point, depth + 1);
} else {
node->right = insert(node->right, point, depth + 1);
}
return node;
}
void search(vector<int> point) {
Node* nearest = search(root, point, 0);
cout << "Nearest point: ";
for (int i = 0; i < nearest->point.size(); i++) {
cout << nearest->point[i] << " ";
}
cout << endl;
}
Node* search(Node* node, vector<int> point, int depth) {
if (node == NULL) {
return NULL;
}
int k = point.size();
int cd = depth % k;
if (point[cd] < node->point[cd]) {
return search(node->left, point, depth + 1);
} else if (point[cd] > node->point[cd]) {
return search(node->right, point, depth + 1);
} else {
if (node->left == NULL && node->right == NULL) {
return node;
}
Node* nearest = nearestNeighbor(node->left, point, depth + 1, node);
if (distance(point, nearest->point) > abs(point[cd] - node->point[cd])) {
nearest = nearestNeighbor(node->right, point, depth + 1, nearest);
}
return nearest;
}
}
Node* nearestNeighbor(Node* node, vector<int> point, int depth, Node* best) {
if (node == NULL) {
return best;
}
if (distance(point, node->point) < distance(point, best->point)) {
best = node;
}
int k = point.size();
int cd = depth % k;
if (point[cd] < node->point[cd]) {
best = nearestNeighbor(node->left, point, depth + 1, best);
if (distance(point, best->point) > abs(point[cd] - node->point[cd])) {
best = nearestNeighbor(node->right, point, depth + 1, best);
}
} else {
best = nearestNeighbor(node->right, point, depth + 1, best);
if (distance(point, best->point) > abs(point[cd] - node->point[cd])) {
best = nearestNeighbor(node->left, point, depth + 1, best);
}
}
return best;
}
int distance(vector<int> a, vector<int> b) {
int d = 0;
for (int i = 0; i < a.size(); i++) {
d += (a[i] - b[i]) * (a[i] - b[i]);
}
return d;
}
};
int main() {
KDTree tree;
tree.insert({3, 6});
tree.insert({17, 15});
tree.insert({13, 15});
tree.insert({6, 12});
tree.insert({9, 1});
tree.search({10, 10});
return 0;
}
```
这个例子实现了一个简单的k-d tree,包括插入和搜索操作。在这个例子中,我们使用了一个结构体Node来表示k-d tree的节点,每个节点包含一个向量point,表示多维空间中的一个点。在插入操作中,我们根据当前节点的深度和向量的某一维的大小来决定将新的点插入到左子树还是右子树中。在搜索操作中,我们首先找到最近的节点,然后递归地搜索左右子树,直到找到最近的点。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)