KD树的构造与Python代码实现

class Node:
    def __init__(self, point, left=None, right=None, axis=None):
        self.point = point    # 节点存储的数据点
        self.left = left      # 左子树
        self.right = right    # 右子树
        self.axis = axis      # 划分轴（维度）

def build_kdtree(points, depth=0):
    """递归构建KD树"""
    if not points:  # 空节点返回None
        return None
    
    k = len(points[0])       # 数据维度
    axis = depth % k         # 根据深度选择划分轴
    
    # 按当前轴排序并选择中位数作为分割点
    points_sorted = sorted(points, key=lambda point: point[axis])
    median_idx = len(points_sorted) // 2
    
    # 递归构建子树
    return Node(
        point=points_sorted[median_idx],
        axis=axis,
        left=build_kdtree(points_sorted[:median_idx], depth + 1),
        right=build_kdtree(points_sorted[median_idx+1:], depth + 1)
    )

def squared_distance(p1, p2):
    """计算两点之间的平方距离"""
    return sum((x - y) ** 2 for x, y in zip(p1, p2))

def nearest_neighbor(root, target):
    """查找目标点的最近邻"""
    best = None          # 当前最近点
    best_dist = float('inf')  # 当前最小距离
    
    def recursive_search(node):
        nonlocal best, best_dist
        
        if node is None:
            return
        
        # 计算当前节点距离
        current_dist = squared_distance(node.point, target)
        if current_dist < best_dist:
            best = node.point
            best_dist = current_dist
        
        # 决定搜索方向
        axis = node.axis
        if target[axis] < node.point[axis]:
            recursive_search(node.left)   # 先搜索左子树
            # 检查右子树是否需要搜索
            if (node.point[axis] - target[axis]) ** 2 < best_dist:  # 
                recursive_search(node.right)
        else:
            recursive_search(node.right)  # 先搜索右子树
            # 检查左子树是否需要搜索
            if (target[axis] - node.point[axis]) ** 2 < best_dist:
                recursive_search(node.left)
    
    recursive_search(root)
    return best

# 示例用法
if __name__ == "__main__":
    
    # 示例数据点（二维）
    points = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
    
    # 构建KD树
    kdtree = build_kdtree(points)
    
    # 查找最近邻
    target = (8, 0.5)
    nearest = nearest_neighbor(kdtree, target)
    print(f"Target: {target}  Nearest: {nearest}")
    
    
 #运行结果：
    Target: (8, 0.5)  Nearest: (8, 1)