KD-Tree (K-Dimensional Tree)

KD-Tree (K-Dimensional Tree)

k차원 공간의 점들을 저장하는 이진 탐색 트리로, 각 레벨에서 다른 차원으로 분할하여 최근접 이웃 검색과 범위 쿼리를 효율적으로 수행

목적: k차원 공간 탐색, 최근접 이웃 검색(KNN), 범위 쿼리, 고차원 인덱싱

특징: 이진 트리, 차원별 순환 분할, 공간 분할, 균형 가능

구조: 레벨 0 = x축 분할, 레벨 1 = y축 분할, ..., 레벨 k = x축 분할(순환)

동작

• •삽입: 현재 차원(depth % k)으로 비교 → 재귀적 삽입
• •검색: 현재 차원 비교 → 탐색 가지치기
• •최근접 이웃(KNN): 우선순위 큐 + 백트래킹, 거리 기반 가지치기

시간 복잡도

• •구축: O(n log n) - 중앙값 분할
• •검색: 평균 O(log n), 최악 O(n)
• •KNN: 평균 O(log n), 고차원에서 O(n)

공간 복잡도: O(n)

장점: 저차원(2-3D)에서 빠른 KNN, 범위 쿼리 효율, 동적 삽입

단점: 고차원의 저주(차원↑ 성능↓), 불균형 가능, 삭제 복잡

적용사례: 최근접 이웃 검색, 이미지 유사도, 머신러닝(KNN), 로봇 경로 계획, 컴퓨터 비전

비교: KD-Tree(k차원/저차원) vs Ball Tree(고차원/메트릭) vs Quadtree(2D/4분할)

연관: KNN, 최근접 이웃, 공간 분할, 범위 쿼리