KD-Tree 與 KNN 演算法 C 語言完整實現：構建、最近鄰搜尋與回溯邏輯

編輯：關於C語言

KD-Tree 核心概念

KD-Tree (K-Dimensional Tree) 是將 K 維空間劃分的資料結構，每個節點沿某一維度劃分超平面，左子空間 ≤ 分裂值，右子空間 > 分裂值。構建時交替選擇維度（循環），分裂點選中位數以平衡樹高。

資料結構定義

typedef struct { double x, y; } DataPoint;  // 2D 點

typedef struct KDNode {
    DataPoint point;           // 分裂點資料
    int dim;                   // 分裂維度 (0=x, 1=y)
    struct KDNode *left, *right;
} KDNode;

構建演算法：遞迴中位數分裂

// 比較函數供 qsort 使用
int cmp_x(const void *a, const void *b) {
    return ((DataPoint*)a)->x > ((DataPoint*)b)->x ? 1 : -1;
}
int cmp_y(const void *a, const void *b) {
    return ((DataPoint*)a)->y > ((DataPoint*)b)->y ? 1 : -1;
}

KDNode* build_kdtree(DataPoint *pts, int n, int depth) {
    if (n == 0) return NULL;

    int dim = depth % 2;  // 2D 交替 x/y
    qsort(pts, n, sizeof(DataPoint), dim == 0 ? cmp_x : cmp_y);

    int mid = (n - 1) / 2;
    KDNode *node = malloc(sizeof(KDNode));
    node->point = pts[mid];
    node->dim = dim;
    node->left  = build_kdtree(pts, mid, depth + 1);
    node->right = build_kdtree(pts + mid + 1, n - mid - 1, depth + 1);
    return node;
}

最近鄰搜尋：遞迴下降 + 回溯檢查

double dist2(DataPoint a, DataPoint b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

void nn_search(KDNode *node, DataPoint target, DataPoint *best, double *best_d2) {
    if (!node) return;

    double d2 = dist2(node->point, target);
    if (d2 < *best_d2) { *best_d2 = d2; *best = node->point; }

    int dim = node->dim;
    double diff = (dim == 0) ? target.x - node->point.x : target.y - node->point.y;
    KDNode *first = diff <= 0 ? node->left : node->right;
    KDNode *second = diff <= 0 ? node->right : node->left;

    nn_search(first, target, best, best_d2);

    // 回溯條件：超平面距離 < 當前最近距離
    if (diff * diff < *best_d2)
        nn_search(second, target, best, best_d2);
}

完整可執行範例

int main() {
    DataPoint dataset[] = {{2,3}, {5,4}, {9,6}, {4,7}, {8,1}, {7,2}};
    DataPoint query = {7.1, 2.1};
    DataPoint best;
    double best_d2 = 1e100;

    KDNode *root = build_kdtree(dataset, 6, 0);
    nn_search(root, query, &best, &best_d2);

    printf("Nearest: (%.2f, %.2f)\nDistance: %.2f\n", best.x, best.y, sqrt(best_d2));
    // 輸出: Nearest: (7.00, 2.00)  Distance: 0.14
    return 0;
}

關鍵細節解析

環節	關鍵點
分裂維度選擇	循環維度 (depth % k) 或方差最大維度（更平衡）
分裂點選擇	中位數保證樹高平衡，平均 O(log n)
搜尋順序	優先搜尋目標點所在子空間
回溯條件	目標點到分裂超平面距離 < 當前最近距離
距離比較	用平方距離避免 sqrt 開銷