이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
K-D 트리(k차원 트리의 약자)는 k차원 공간에서 점을 구성하기 위한 공간 분할 데이터 구조입니다. K-D 트리는 다차원 검색 키를 포함하는 검색(예: 범위 검색 및 최근접 이웃 검색)과 같은 여러 응용 프로그램에 유용한 데이터 구조입니다.
K-D 트리는 각 내부 노드가 k 차원 공간의 한 지점을 나타내는 이진 트리입니다. 트리는 k 차원 중 하나의 중앙값을 따라 공간의 점을 두 개의 절반으로 재귀적으로 분할하여 구성됩니다. 이 과정은 모든 포인트가 트리의 리프에 포함될 때까지 재귀적으로 반복됩니다.
K-D 트리는 O(n log n) 시간에 구성할 수 있습니다. 여기서 n은 공간의 포인트 수입니다.
구성 알고리즘은 무작위로 차원(k-dimension)을 선택하는 것으로 시작합니다. 그런 다음 이 차원을 따라 포인트가 정렬되고 중간 포인트가 트리의 루트로 선택됩니다. 중앙값의 왼쪽에 있는 점은 재귀적으로 왼쪽 하위 트리로 분할되고 중앙값의 오른쪽에 있는 점은 오른쪽 하위 트리로 재귀적으로 분할됩니다. 이 프로세스는 모든 포인트가 트리의 리프에 포함될 때까지 반복됩니다.
쿼리 포인트 q가 주어지면 트리를 순회하여 O(log n) 시간 내에 q의 가장 가까운 이웃을 찾을 수 있습니다. 검색은 트리의 루트에서 시작하여 다음과 같이 진행됩니다.
리프 노드에 도달하면 검색이 종료됩니다. 이 시점에서 q의 가장 가까운 이웃은 q에 가장 가까운 리프 노드의 점입니다.
K-D 트리는 주어진 쿼리 지점에 가장 가까운 공간에서 지점을 찾는 데 사용되는 검색 유형인 최근접 이웃 검색에 일반적으로 사용됩니다. 최근접 이웃 검색은 패턴 인식 및 컴퓨터 그래픽과 같은 애플리케이션에서 자주 사용됩니다.
K-D 트리는 쿼리 지점의 지정된 거리 내에 있는 공간의 모든 지점을 찾는 데 사용되는 검색 유형인 범위 검색에도 사용됩니다. 범위 검색은 과학적 시각화 및 지리 정보 시스템과 같은 응용 프로그램에서 자주 사용됩니다.