K-d 트리

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

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

자료 구조
기하 자료 구조
컴퓨터 그래픽스 자료 구조