KD트리가 필요한 이유와 특징

목차

1. KD트리가 필요한 이유와 특징
2. KD트리의 검색, 삽입 삭제 연산

본문내용

K-차원(DIMENSINAL)는 k차원 공간의 점들을 구조화 하는 공간 분할 자료구조인데 다차원 탐색 키에 관련된 같은 적용 분야에 유용한 자료구조이다. 모든 노드가 k차원 점인 이진 트리며 모든 리프 노드는 암시적으로 공간을 반평면의 두 부분으로 나누는 분할 평면을 만드는 것인데 이 초평면의 왼쪽은 그 노드의 왼쪽 부분 트리를 나타내고 오른쪽은 오른쪽 부분 트리를 나타낸다. 이진 검색트리를 확장하여 k개(k>=2)의 필드로 이루어지는 키를 사용하며 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다.
다차원의 점 데이터를 인덱스할 수 있는 가장 간단하면서도 기본적인 데이터구조여서 kd트리는 일반적으로 디스크 저장을 고려하지않고 주기억장치 상에서 동작하는 인덱스구조이다.
대용량 데이터에는 적당하지않고 소규모 다차원 점 데이터를 인덱스할 때 적합하다.

참고자료

· 강의노트 ‘알고리즘’
· 이것이 자바다
· codingstorywithme.tistory.com/3
· ichi.pro/ko/k-chawon-teuli-ihae-31731051093794