K-d 트리 문서 원본 보기

{{위키데이터 속성 추적}}
{{DISPLAYTITLE:''k''-d 트리}}
{{자료 구조 정보
|name= ''k''-d 트리
|type= 다차원 [[이진 탐색 트리|BST]]
|invented_by= [[존 벤틀리]]
|invented_year= 1975
|
|space_avg= <math>O(n)</math>
|space_worst= <math>O(n)</math>
|search_avg= <math>O(\log n)</math>
|search_worst= <math>O(n)</math>
|insert_avg= <math>O(\log n)</math>
|insert_worst= <math>O(n)</math>
|delete_avg= <math>O(\log n)</math>
|delete_worst= <math>O(n)</math>
}}

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

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

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

{{토막글|컴퓨터 과학}}

[[분류:자료 구조]]
[[분류:기하 자료 구조]]
[[분류:컴퓨터 그래픽스 자료 구조]]