K-D 树 (K-D Tree)

Published: Wed Feb 18 2026 | Modified: Wed Feb 18 2026 , 4 minutes reading.

K-D 树：维度切割者

算法背后的故事：切蛋糕

想象你有一块充满葡萄干（数据点）的奶酪（3D 空间）。你想整理它以便能快速找到葡萄干。

与其把它切成微小的立方体（像网格一样），你决定一次切一刀。

第一刀 (X 轴)： 垂直地将奶酪切成两半。左边是“西”，右边是“东”。
第二刀 (Y 轴)： 现在，对每一半，水平切一刀。上面是“北”，下面是“南”。
第三刀 (Z 轴)： 现在，对每一块，按深度切一刀。前面 vs 后面。
重复： 回到 X 轴。

这就是 K-D 树 (K-Dimensional Tree)。它通过在维度之间循环来划分空间。它是“最近邻搜索 (Nearest Neighbor Search)”的标准算法。

为什么需要它？

天文学： “找出 3D 空间中离地球最近的 5 颗恒星。”
机器学习 (KNN)： “找出与 Luke 最相似的 10 个用户。”（如果用户是一个 [年龄, 收入, 位置] 的向量，这就是一个 3D 搜索）。
颜色匹配： “在我们的调色板中找出与这种红色最接近的颜色”（RGB 是 3D 空间）。

算法是如何“思考”的

这个算法是一棵交替二叉搜索树。

枢轴 (Pivot)： 在每一层 depth，我们选择一个维度 axis = depth % k（例如，如果 k=2，轴就是 0->X, 1->Y, 0->X…）。
中位数 (Median)： 我们沿着该轴对点进行排序，并选取中位数点作为节点。
递归：
- 坐标较小的点去左边。
- 坐标较大的点去右边。

最近邻搜索逻辑：

它就像在 BST 中找叶子节点。
但当我们回溯（展开递归）时，我们要检查：“在切割面的另一侧是否可能存在更近的点？”
如果到“切割平面”的距离小于到我们“当前最佳邻居”的距离，我们必须去另一侧看看。否则，我们可以剪掉整个分支。

工程决策：高维诅咒

K-D 树在低维（2D, 3D）下表现惊人。但当维度很高时（>20），它们会失效。

问题： 在 100 维空间中，几乎每一个分支都需要被检查，因为“一切都很远”。
解决方案： 对于高维数据（例如 128 维的人脸识别向量），工程师使用 LSH (局部敏感哈希) 或 HNSW (分层可导航小世界图) 来代替精确树。

实现参考 (Python)

import operator

class Node:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right

def build_kdtree(points, depth=0):
    if not points:
        return None
    
    k = len(points[0]) # 维度数量
    axis = depth % k   # 交替轴: 0, 1, 2...
    
    # 按当前轴排序点并选中位数
    points.sort(key=lambda x: x[axis])
    median = len(points) // 2
    
    return Node(
        point=points[median],
        left=build_kdtree(points[:median], depth + 1),
        right=build_kdtree(points[median+1:], depth + 1)
    )

def distance_squared(p1, p2):
    return sum((a - b)**2 for a, b in zip(p1, p2))

def closest_point(root, target, depth=0, best=None):
    if root is None:
        return best
    
    k = len(target)
    axis = depth % k
    
    next_best = None
    next_branch = None
    opposite_branch = None

    # 如果当前节点更近，更新最佳点
    dist = distance_squared(root.point, target)
    if best is None or dist < distance_squared(best, target):
        next_best = root.point
    else:
        next_best = best

    # 决定走哪边
    if target[axis] < root.point[axis]:
        next_branch = root.left
        opposite_branch = root.right
    else:
        next_branch = root.right
        opposite_branch = root.left

    # 先递归进入“好”的那一边
    next_best = closest_point(next_branch, target, depth + 1, next_best)

    # 检查我们是否需要跨越边界？
    # 到平面的距离是否小于到当前最佳点的距离？
    if (target[axis] - root.point[axis])**2 < distance_squared(next_best, target):
        next_best = closest_point(opposite_branch, target, depth + 1, next_best)

    return next_best

# 使用示例
points = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
tree = build_kdtree(points)
target = (9, 2)
print(f"离 {target} 最近的点: {closest_point(tree, target)}")

小结

K-D 树教会我们：复杂性可以通过轮流处理来管理。通过将一个多维问题简化为一系列的一维决策，我们可以高效地在复杂空间中导航。它提醒我们，无论世界多么复杂，我们通常可以一次切一个角度来解构它。

Luke Sun