k-d 트리 (K-Dimensional Tree)

"이 좌표에서 가장 가까운 점은?" — 점이 100만 개면 전부 거리를 재는 건 너무 느리다. k-d 트리는 평면을 축을 번갈아 가며 반씩 잘라 이진 트리로 만들어, 볼 필요 없는 영역을 통째로 건너뛴다.

1. 브루트 포스는 왜 느릴까

질의점 q 하나에 대해 최근접 점을 찾으려면, 소박하게는 모든 점과의 거리를 계산해 최솟값을 고른다. 점이 N개면 질의 하나에 O(N). 지도에 매장 50만 개, 매 프레임 수천 번 질의라면 감당이 안 된다.

k-d 트리는 점들을 미리 O(N log N)에 정리해 두고, 질의를 평균 O(log N)에 답한다. 핵심 아이디어: "질의점에서 지금까지 찾은 최선 거리보다, 저 영역 경계가 더 멀면 그 영역은 볼 필요가 없다."

2. 트리 만들기 — 축을 번갈아 자른다

깊이 0에서는 x 좌표 기준으로, 깊이 1에서는 y 좌표 기준으로, 깊이 2에서 다시 x … 이렇게 차원을 돌아가며 나눈다. 각 단계에서 해당 축의 중앙값(median) 점을 노드로 삼으면 트리가 균형 잡힌다.

def build(points, depth=0):
    if not points: return None
    axis = depth % 2                    # 0 = x축, 1 = y축
    points.sort(key=lambda p: p[axis])
    mid = len(points) // 2            # 중앙값 = 균형
    return Node(
        point = points[mid],
        axis  = axis,
        left  = build(points[:mid],   depth+1),   # 이 축에서 더 작은 점들
        right = build(points[mid+1:], depth+1),  # 더 큰 점들
    )

아래에서 왼쪽 평면을 클릭해 점을 추가해 보자. 파란 선은 x 분할, 주황 선은 y 분할이다. 오른쪽에 대응하는 이진 트리가 함께 그려진다.

3. 최근접 이웃 탐색 — 가지치기가 핵심

위 데모에서 「최근접 탐색 모드」를 켜고 평면을 클릭하면 질의점 q가 놓이고, 탐색 과정이 로그에 단계별로 찍힌다. 알고리즘은 이렇게 움직인다.

1. 내려가기: 루트부터 시작해, 각 노드의 분할축에서 q가 노드보다 작으면 왼쪽, 크면 오른쪽으로 내려간다. 리프에 닿으면 그 점을 일단 "현재 최선(best)"으로 잡는다.
2. 거슬러 올라오며 확인: 부모로 돌아오면서, 부모 노드 자신과의 거리도 재서 best를 갱신한다.
3. 반대편을 볼까 말까 (가지치기): 부모의 분할선까지의 거리가 지금 best 거리보다 멀면, 반대편 서브트리에는 더 가까운 점이 있을 수 없다 → 통째로 건너뛴다. 가까우면 반대편도 재귀로 들어간다.

def nearest(node, q, best):
    if node is None: return best
    d = dist(node.point, q)
    if d < best.dist: best = (node.point, d)

    axis = node.axis
    diff = q[axis] - node.point[axis]
    near, far = (node.left, node.right) if diff < 0 else (node.right, node.left)

    best = nearest(near, q, best)              # 1) 가까운 쪽 먼저
    if abs(diff) < best.dist:                  # 2) 분할선이 best보다 가까울 때만
        best = nearest(far, q, best)          #    반대편도 확인
    return best

4. 직접 비교: 방문 노드 수

탐색 모드에서 질의를 여러 번 해보면, 방문 노드 수가 브루트 포스(전체 점 수) 보다 훨씬 작은 걸 볼 수 있다. 점을 30개 정도 뿌리고 시도해 보자. 다만 질의점이 점 구름에서 멀리 떨어져 있거나 점이 몰려 있으면 가지치기가 덜 되어 방문 수가 늘어난다.

5. 복잡도와 한계

• 차원의 저주: 차원 k가 커지면(대략 k > 10~20) 가지치기가 거의 안 먹혀 브루트 포스와 비슷해진다. 고차원에서는 근사 방법(Ball tree, HNSW, LSH)을 쓴다.
• 동적 데이터에 약함: 점이 계속 추가/삭제되면 트리가 기울어진다. 주기적으로 재구성하거나 R-tree 계열을 쓴다.
• 2~3차원 + 대체로 고정된 점이면 k-d 트리가 가장 단순하고 빠른 선택이다.

6. 쿼드트리와 뭐가 다를까