기본 개념
다차원 이진 탐색 트리(약칭 k-d 트리)는 다중 키 레코드를 저장하기 위한 데이터 구조로 정의됩니다. 이 구조는 통계 및 데이터 분석에서 여러 "기하학적" 문제를 해결하기 위해 구현되었습니다.
k-d 트리(k-차원 트리의 약어)는 k-차원 공간에서 점을 구성하기 위한 공간 분할 데이터 구조로 정의됩니다. 데이터 구조 k-d 트리는 다차원 검색 키를 포함하는 검색(예:범위 검색 및 최근접 이웃 검색)과 같은 여러 응용 프로그램에 대해 구현됩니다. k-d 트리는 이진 공간 분할 트리의 특수한 경우로 취급됩니다.
비공식적인 설명
k-d 트리는 모든 리프 노드가 k-차원 점으로 처리되는 이진 트리입니다. 리프가 아닌 모든 노드는 공간을 절반 공간이라고 하는 두 부분으로 나누는 분할 초평면(중앙값으로 사용)을 암시적으로 생성하는 것으로 상상할 수 있습니다. 이 초평면의 왼쪽에 있는 점은 해당 노드의 왼쪽 하위 트리로 처리되고 초평면의 오른쪽에 있는 점은 오른쪽 하위 트리에서 처리됩니다. 다음과 같은 방식으로 초평면 방향을 선택할 수 있습니다. 트리의 모든 노드는 해당 차원의 축에 수직인 초평면과 함께 k 차원 중 하나와 연결됩니다. 예를 들어, 특정 분할에 대해 "x" 축이 선택되면 노드보다 "x" 값이 작은 하위 트리의 모든 포인트가 왼쪽 하위 트리에 나타나고 "x" 값이 더 높은 모든 포인트는 오른쪽 하위 트리에서. 이 경우 초평면은 점의 x 값으로 설정되고 법선은 단위 x 축을 나타냅니다. 인기 있는 방법은 무작위로 선택한 고정된 수의 점을 정렬하고 해당 점의 중앙값을 구현하여 분할 평면으로 사용하는 것입니다.
n개의 포인트 목록이 주어지면 다음 알고리즘은 중앙값 찾기 정렬을 사용하여 해당 포인트를 포함하는 균형 잡힌 k-d 트리를 만듭니다.
function KDtree (list of points PointList, int Depth) {
// Choose axis based on Depth so that axis cycles through all valid values
var int axis := Depth mod k;
// Sort point list and select median as pivot element
choose median by axis from PointList;
// Node is created as node1 and construct subtree
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;
}