KD 트리(K-Dimensional Tree, K-차원 트리)

1. KD 트리의 핵심 원리

• 2차원, 3차원, 혹은 그 이상의 다차원 공간에 있는 포인트들을 효율적으로 분할하고 탐색하기 위해 설계된 이진 탐색 트리
• KD 트리는 각 레벨마다 번갈아가며 다른 축(Dimension)을 기준으로 데이터를 분할
• 예를 들어, 2차원 좌표 (x, y$ 데이터들을 KD 트리에 삽입한다고 가정하면
  1. 루트 노드 (레벨 0): x축을 기준으로 정렬한 뒤, 중간값(Median)을 기준으로 공간을 왼쪽, 오른쪽으로 반으로 나눔
  2. 자식 노드 (레벨 1): 이번에는 y축을 기준으로 정렬한 뒤, 중간값을 기준으로 위, 아래로 반을 나눔
  3. 손자 노드 (레벨 2): 다시 x축을 기준으로 나눔
  4. 이 과정을 데이터가 하나씩 남을 때까지 번갈아가며 반복
• 데이터 셋: A(2,3), B(5,4), C(9,6), D(4,7), E(8,1), F(7,2)

             [ 루트: B(5,4) ] (x축 기준 분할)
             /        \
     [ A(2,3) ]      [ F(7,2) ] (y축 기준 분할)
        /   \          /    \
      (None) [D(4,7)] [E(8,1)] [C(9,6)] (x축 기준 분할)

 

2. 주요 용도 (어디에 쓰일까?)

• KD 트리는 다차원 공간에서 특정 조건에 맞는 점들을 빠르게 찾을 때 최고의 성능을 발휘
• 최근접 이웃 탐색 (Nearest Neighbor Search): 특정 위치에서 가장 가까운 데이터를 찾을 때 사용 (예: 지도 앱에서 내 위치에서 가장 가까운 주유소 찾기)
• 범위 검색 (Range Search): 특정 영역(사각형이나 구 형태) 내에 존재하는 모든 점을 찾을 때 사용
• 머신러닝 (KNN 알고리즘): K-최근접 이웃(K-Nearest Neighbors) 분류 알고리즘을 구현할 때, 일일이 모든 데이터와 거리를 비교하면 너무 느리기 때문에 KD 트리를 사용해 속도를 높임
• 컴퓨터 그래픽스: 3차원 그래픽스에서 광선 추적(Ray Tracing)이나 충돌 감지(Collision Detection)를 할 때 공간을 분할하는 용도로 쓰임

 

3. KD 트리의 장점과 한계

장점

• 빠른 탐색 속도: 데이터가 고르게 분포되어 있다면, 평균적으로 $O(\log N)$의 시간 복잡도로 가장 가까운 점을 찾거나 특정 범위를 탐색할 수 있습니다. 공간을 절반씩 날려버리며 탐색하기 때문입니다.

한계 (차원의 저주)

• 고차원에서의 성능 저하: 데이터의 차원($K$)이 너무 커지면(대략 20차원 이상), 트리의 대부분의 가지를 다 뒤져야 하는 상황이 발생합니다. 결국 모든 데이터와 일일이 거리를 비교하는 전수 조사($O(N)$)와 속도가 비슷해지는데, 이를 차원의 저주(Curse of Dimensionality)라고 합니다.
• 데이터 삽입/삭제의 취약함: 데이터가 중간에 새로 추가되거나 삭제되면 트리의 균형이 깨지기 쉽고, 균형을 다시 맞추는(Rebalancing) 비용이 큽니다. 따라서 주로 정적인 데이터(변하지 않는 데이터)를 한 번에 빌드해서 사용할 때 유용합니다.