기본 개념
다차원 이진 탐색 트리(multidimensional binary search tree), 흔히 k-d 트리라고 불리는 자료구조는 여러 개의 키(multikey)를 가진 레코드를 저장하기 위해 고안된 구조입니다. 통계학과 데이터 분석 분야에서 다양한 '기하학적' 문제를 해결하기 위해 널리 활용되어 왔습니다.
k-d 트리(k-dimensional tree)는 k차원 공간에 존재하는 점들을 체계적으로 조직화하기 위한 공간 분할(space-partitioning) 자료구조로 정의됩니다. 다차원 검색 키를 사용하는 연산, 예를 들어 범위 검색(range search)이나 최근접 이웃 검색(nearest neighbor search) 같은 응용에 적합하며, 이진 공간 분할 트리(binary space partitioning tree)의 특수한 사례로 간주됩니다.
직관적인 설명
k-d 트리는 모든 리프 노드가 k차원 공간의 한 점(point)을 나타내는 이진 트리입니다. 리프가 아닌 각 노드는 암묵적으로 하나의 분할 초평면(splitting hyperplane)을 생성하며, 이 초평면은 공간을 두 개의 반공간(half-space)으로 나눕니다. 초평면 왼쪽에 위치한 점들은 해당 노드의 왼쪽 서브트리가 담당하고, 오른쪽에 위치한 점들은 오른쪽 서브트리가 담당합니다.
초평면의 방향은 다음과 같은 방식으로 결정할 수 있습니다. 트리의 모든 노드는 k개의 차원 중 하나와 연결되며, 그 차원의 축에 수직인 초평면을 기준으로 삼습니다. 예를 들어 특정 분할 단계에서 'x' 축이 선택되었다면, x 값이 노드보다 작은 점들은 모두 왼쪽 서브트리에, x 값이 큰 점들은 오른쪽 서브트리에 배치됩니다. 이때 초평면은 해당 점의 x 값으로 설정되고, 그 법선(normal)은 x축 단위 벡터를 가리킵니다.
실제 구현에서는 무작위로 선정한 일정 수의 점들을 정렬한 뒤, 그 중앙값(median)을 분할 평면으로 사용하는 방식이 널리 쓰입니다. 이렇게 하면 트리가 한쪽으로 치우치는 것을 막아 균형 잡힌 구조를 유지할 수 있습니다.
균형 잡힌 k-d 트리 생성 알고리즘
n개의 점이 주어졌을 때, 아래 의사 코드는 중앙값 찾기 정렬을 이용해 균형 잡힌 k-d 트리를 재귀적으로 구성합니다.
function KDtree (list of points PointList, int Depth) {
// Depth를 기준으로 축을 선택해 모든 유효한 값이 순환하도록 함
var int axis := Depth mod k;
// 점 목록을 정렬하고 중앙값을 피벗 요소로 선택
choose median by axis from PointList;
// node1을 생성하고 서브트리를 구성
node1.location := median;
node1.leftChild := KDtree(points in PointList before median, Depth+1);
node1.rightChild := KDtree(points in PointList after median, Depth+1);
return node1;
}주요 특징과 활용 분야
k-d 트리는 데이터가 비교적 고르게 분포되어 있을 때 최근접 이웃 검색을 평균적으로 O(log n)의 시간 복잡도로 처리할 수 있습니다. 다만 데이터 분포가 치우친 최악의 경우 성능이 O(n)까지 저하될 수 있으므로, 중앙값 기반 분할을 통한 균형 유지가 중요합니다.
이러한 특성 덕분에 k-d 트리는 컴퓨터 그래픽스(광선 추적), 로봇 공학의 경로 계획, 머신러닝의 k-NN 분류, 지리 정보 시스템(GIS), 추천 시스템 등 다차원 좌표 데이터를 빠르게 검색해야 하는 다양한 분야에서 폭넓게 활용되고 있습니다.