KDTree 代码实现

KDTree（K-Dimensional Tree），也称为kd树，是一种用于高效搜索、插入和删除点数据的数据结构，特别是在高维空间中。它通过将空间划分为超立方体，并将每个节点分割到其子节点中的一维上，形成一棵分层的二叉树。

以下是Python中简单实现的一个基本KDTree的例子：

import numpy as np

class KDNode:
    def __init__(self, point=None, is_leaf=True, axis=0):
        self.point = point
        self.axis = axis
        self.left = None
        self.right = None
        self.is_leaf = is_leaf

class KDTree:
    def __init__(self, points=None):
        if points is not None:
            self.root = self._build_kdtree(points)

    def _build_kdtree(self, points, axis=0):
        if len(points) == 0:
            return None
        else:
            # 获取轴索引下的最小值点
            min_point = min(points, key=lambda x: x[axis])
            non_min_points = [p for p in points if p != min_point]
            
            if len(non_min_points) == 0:
                return KDNode(min_point, True)
                
            # 将剩余点沿当前轴划分
            split = {True: [], False: []}
            for p in non_min_points:
                if p[axis] < min_point[axis]:
                    split[True].append(p)
                else:
                    split[False].append(p)

            # 递归构建左子树和右子树
            left_axis = (axis + 1) % len(points[0])
            right_axis = (axis - 1) % len(points[0])

            self.root.left = self._build_kdtree(split[True], left_axis)
            self.root.right = self._build_kdtree(split[False], right_axis)

            return KDNode(min_point, False, axis)

    def search(self, target):
        return self._search(self.root, target)

    def _search(self, node, target):
        if node is None or node.is_leaf:
            return []
        
        if target[node.axis] < node.point[node.axis]:
            return self._search(node.left, target)
        elif target[node.axis] > node.point[node.axis]:
            return self._search(node.right, target)
        else:
            results = self._search(node.left, target)
            results.extend(self._search(node.right, target))
            return results

这个例子创建了一个`KDTree`类，包含了构造函数（初始化和构建kd树）、搜索功能等。你可以使用`search`方法查找是否包含某个点。