python 实现kd树构造和搜索

在Python中，KD树（K-Dimensional Tree）是一种用于数据结构和算法的数据组织形式，特别适合于查找、插入和删除二维或三维空间中的点。以下是构建和搜索的基本步骤：

**构建 KD 树（Construction）**：
1. **选择轴向**：从输入数据集中随机选择一个特征作为分割轴（通常是第一个特征，然后逐次添加其他特征）。
2. **划分数据**：将数据集根据选定的轴分成两部分，形成两个子集合。
3. **递归构建**：对每个子集合分别递归地创建一个新的KD树节点，并将其设置为当前节点的子节点。
4. **终止条件**：当子集中的元素少于某个阈值（如5或10），或者没有更多的特征可用时，创建一个叶子节点，存储剩余的点。

**搜索 KD 树（Search）**：
1. **比较当前节点**：如果目标点的特征值与当前节点的特征值相等，则直接返回该节点；否则，根据特征值的大小和方向选择左子树或右子树。
2. **递归向下搜索**：继续在子树中对比，直到找到匹配的目标点，或者到达叶节点。
3. **回溯结果**：如果在叶节点找到了目标，就返回搜索路径；如果没有找到，则表示未找到。

**示例代码**：

from sklearn.neighbors import KDTree

# 构建KD树
points = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1)]
tree = KDTree(points)

# 搜索特定点
query_point = (6, 5)
distances, indices = tree.query(query_point, k=2)  # 返回最近的k个点