K-D 樹：維度切割者

演算法背後的故事：切蛋糕

想像妳有一塊充滿葡萄乾（數據點）的奶酪（3D 空間）。妳想整理它以便能快速找到葡萄乾。

與其把它切成微小的立方體（像網格一樣），妳決定一次切一刀。

1. 第一刀 (X 軸)： 垂直地將奶酪切成兩半。左邊是「西」，右邊是「東」。
2. 第二刀 (Y 軸)： 現在，對每一半，水平切一刀。上面是「北」，下面是「南」。
3. 第三刀 (Z 軸)： 現在，對每一塊，按深度切一刀。前面 vs 後面。
4. 重複： 回到 X 軸。

這就是 K-D 樹 (K-Dimensional Tree)。它透過在維度之間循環來劃分空間。它是「最近鄰搜尋 (Nearest Neighbor Search)」的標準演算法。

為什麼需要它？

• 天文學： 「找出 3D 空間中離地球最近的 5 顆恆星。」
• 機器學習 (KNN)： 「找出與 Luke 最相似的 10 個用戶。」（如果用戶是一個 [年齡, 收入, 位置] 的向量，這就是一個 3D 搜尋）。
• 顏色匹配： 「在我們的調色板中找出與這種紅色最接近的顏色」（RGB 是 3D 空間）。

演算法是如何「思考」的

這個演算法是一棵交替二叉搜尋樹。

1. 樞軸 (Pivot)： 在每一層 depth，我們選擇一個維度 axis = depth % k（例如，如果 k=2，軸就是 0->X, 1->Y, 0->X…）。
2. 中位數 (Median)： 我們沿著該軸對點進行排序，並選取中位數點作為節點。
3. 遞迴：
   • 座標較小的點去左邊。
   • 座標較大的點去右邊。

最近鄰搜尋邏輯：

• 它就像在 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 樹教會我們：複雜性可以透過輪流處理來管理。透過將一個多維問題簡化為一系列的一維決策，我們可以高效地在複雜空間中導航。它提醒我們，無論世界多麼複雜，我們通常可以一次切一個角度來解構它。