k-d 트리

컴퓨터 과학에서 k-d 트리(영어: k-d tree, k-차원(dimensional) 트리)는 k차원 공간의 점들을 구조화하는 공간 분할 자료 구조이다. k-d 트리는 다차원 탐색 키에 관련된 탐색 같은 적용분야에 유용한 자료구조이다(예: 범위 탐색과 최근접 이웃 탐색). k-d 트리는 이진 공간 분할 트리의 특수한 경우이다.

k-d 트리
종류	다차원 BST
발명일	1975
발명자	존 벤틀리
점근표기법으로 된 시간복잡도
알고리즘 평균 최악의 경우 공간 $O(n)$ $O(n)$ 탐색 $O(\log n)$ $O(n)$ 삽입 $O(\log n)$ $O(n)$ 삭제 $O(\log n)$ $O(n)$

3차원 k-d 트리. 첫번째 분할(빨간색 수직면)은 루트 셀(흰 색)을 두 부분 셀로 나누고, 각각의 부분 셀은 두 부분 셀로 (초록색 수평면으로) 분할한다. 결국은, 이 네 셀들은 또 두 부분 셀로 분할(네 파란색 수직면)한다. 더 이상은 분할이 없기 때문에, 최종 여덟 셀들은 리프 셀이라고 불린다.

비공식적 설명

k-d 트리는 모든 노드가 k차원 점인 이진 트리이다. 모든 리프 노드는 암시적으로 공간을 반평면의 두 부분으로 나누는 분할 초평면을 만드는 것으로 생각할 수 있다. 이 초평면의 왼쪽은 그 노드의 왼쪽 부분 트리를 나타내고 오른쪽은 오른쪽 부분 트리를 나타낸다. 초평면의 방향은 다음과 같이 결정된다: 트리에 있는 모든 노드는 k차원 중 하나와 연관되어 있으며, 그 초평면은 그 차원축에 수직한다. 따라서 예를 들어 보면, 수직 분할할 대상으로 "x"축을 선택했으면 노드보다 더 작거나 같은 "x"값을 가지는 부분트리의 모든 점은 왼쪽 부분트리에 속하고 더 큰 점은 오른쪽에 속한다.