정의 k-d 트리는 k차원 공간에 있는 점들을 조직화하기 위한 공간 분할 자료구조(space-partitioning data structure)이다. 주로 컴퓨터 과학 분야에서 최근접 이웃 탐색(nearest neighbor search), 범위 탐색(range search) 등과 같은 기하학적 탐색 문제들을 효율적으로 해결하기 위해 사용된다. 여기서 'k-d'는 'k-dimensional'(k차원)을 의미한다.
개요 k-d 트리는 이진 탐색 트리의 개념을 다차원 공간으로 확장한 것으로 볼 수 있다. 각 노드는 k차원 공간 내의 하나의 점을 저장하며, 해당 노드를 기준으로 공간을 두 개의 하이퍼플레인(hyperplane)으로 분할한다. 이 분할 과정은 각 차원(축)을 번갈아가며 재귀적으로 이루어져, 결과적으로 공간이 더 작은 영역들로 나뉘게 된다. 이러한 구조 덕분에, 주어진 질의점(query point)과 가장 가까운 점을 찾거나 특정 영역 안에 포함되는 모든 점을 찾는 등의 연산을 효율적으로 수행할 수 있다.
어원/유래 k-d 트리는 1975년 존 벤틀리(Jon Bentley)가 "Multidimensional Binary Search Trees Used for Associative Searching"이라는 논문에서 처음 제안하였다. 그는 이 자료구조를 통해 다차원 데이터에 대한 효율적인 탐색 방법을 제시했으며, 이후 k-d 트리는 컴퓨터 그래픽스, 로봇 공학, 기계 학습 등 다양한 분야에서 널리 활용되었다. 'k-d'라는 명칭은 다루는 데이터의 차원(dimension)이 'k'개라는 특징을 직접적으로 나타낸다.
특징
- 구조 및 분할 방식: k-d 트리는 기본적으로 이진 트리 형태를 갖는다. 각 내부 노드는 하나의 k차원 점을 저장하며, 이 점을 기준으로 특정 차원(축)에 수직인 하이퍼플레인을 사용하여 공간을 두 개의 반공간(half-space)으로 분할한다. 트리 깊이가 깊어질수록 분할에 사용되는 차원은 순환적으로 변경된다 (예: 0번째 깊이에서는 x축, 1번째 깊이에서는 y축, 2번째 깊이에서는 z축, 3번째 깊이에서는 다시 x축 등).
- 균형 잡힌 트리: 이상적인 k-d 트리는 각 서브트리에 대략적으로 동일한 수의 점이 포함되도록 구축되어야 한다. 이는 중간값을 기준으로 분할함으로써 달성될 수 있으며, 이를 통해 트리의 높이를 최소화하고 탐색 효율성을 높일 수 있다.
- 탐색 연산:
- 삽입(Insertion): 새로운 점을 삽입할 때는 루트부터 시작하여 해당 점이 속하는 하위 공간을 찾아 내려가며, 최종적으로 리프 노드에 삽입한다.
- 삭제(Deletion): 삭제 연산은 삽입보다 복잡하며, 트리의 균형을 유지하면서 효율적으로 수행하기 위한 여러 전략이 존재한다.
- 최근접 이웃 탐색(Nearest Neighbor Search): 특정 점에 가장 가까운 점을 찾는다. 트리를 탐색하며 현재까지 발견된 최단 거리를 기반으로 탐색 공간을 가지치기(pruning)하여 효율성을 높인다.
- 범위 탐색(Range Search): 주어진 범위(직사각형, 구형 등) 내에 포함되는 모든 점을 찾는다.
- 장점:
- 저차원 및 중간 차원(k가 2~20 정도)의 데이터에서 최근접 이웃 탐색, 범위 탐색 등 기하학적 질의에 매우 효율적이다.
- 구현이 비교적 간단하다.
- 단점:
- 차원의 저주(Curse of Dimensionality): k가 매우 커지면(고차원 데이터) 트리의 깊이가 깊어지고, 가지치기의 효과가 줄어들어 탐색 성능이 선형 탐색과 비슷해지는 경향이 있다.
- 데이터의 분포에 따라 트리의 균형이 깨질 수 있으며, 이 경우 성능이 저하될 수 있다.
- 정적 데이터셋에 더 적합하며, 동적인 데이터셋(잦은 삽입/삭제)에서는 트리의 균형을 유지하는 데 추가적인 비용이 발생할 수 있다.
관련 항목
- 공간 분할 자료구조 (Space-partitioning data structure)
- 최근접 이웃 탐색 (Nearest neighbor search)
- 범위 탐색 (Range search)
- 옥트리 (Octree)
- 쿼드트리 (Quadtree)
- 이진 공간 분할 트리 (Binary Space Partitioning tree, BSP tree)
- 차원의 저주 (Curse of dimensionality)