[c++] kd-트리 검색 알고리즘

15 Dec 2023

KD 트리는 k차원 공간에서의 효율적인 검색을 위한 자료 구조입니다. “k”는 차원 수를 나타냅니다. 이 구조는 k차원 공간을 잘게 나누어 저장하고 검색함으로써 공간 내의 점들에 대한 빠른 검색을 가능하게 합니다.

KD 트리의 작동 방식

KD 트리는 이진 트리의 한 형태로, 각 노드는 k차원 공간에서의 한 점을 나타냅니다. 각 레벨마다 다른 차원의 좌표축을 기준으로 트리를 잘게 나눕니다. 예를 들어, 2차원 공간의 경우, 첫 번째 레벨은 x축에 대해, 두 번째 레벨은 y축에 대해 트리를 나눕니다.

검색 알고리즘

삽입

KD 트리에 노드를 추가할 때, 각 레벨에서 해당하는 차원의 좌표를 기준으로 트리를 내려가며 적절한 위치를 찾아 삽입합니다.

void insert(Node* root, Node* newNode, int level) {
    if (root == NULL) {
        root = newNode;
    } else {
        if (newNode->point[level] < root->point[level]) {
            insert(root->left, newNode, (level + 1) % k);
        } else {
            insert(root->right, newNode, (level + 1) % k);
        }
    }
}

검색

주어진 점에 가장 가까운 이웃을 찾기 위해서는, 트리를 내려가며 주어진 점 주변의 지역을 탐색해야 합니다.

void searchNearest(Node* root, Node* target, int level, Node* best) {
    if (root == NULL) {
        return;
    }
    if (distance(root->point, target) < distance(best->point, target)) {
        best = root;
    }
    int axis = level % k;
    if (target->point[axis] < root->point[axis]) {
        searchNearest(root->left, target, (level + 1) % k, best);
        if (pow(target->point[axis] - root->point[axis], 2) < distance(best->point, target)) {
            searchNearest(root->right, target, (level + 1) % k, best);
        }
    } else {
        searchNearest(root->right, target, (level + 1) % k, best);
        if (pow(target->point[axis] - root->point[axis], 2) < distance(best->point, target)) {
            searchNearest(root->left, target, (level + 1) % k, best);
        }
    }
}

KD 트리는 고차원 데이터에 대한 효율적인 검색을 위한 좋은 선택지일 수 있습니다. 그러나 데이터셋의 특성에 따라 효율성이 달라질 수 있으므로, 실제 사용에 앞서 성능과 trade-off를 신중히 고려해야 합니다.

참고 자료: GeeksforGeeks