KD-트리
- 각 레벨에서 필드를 번갈아 가며 검색에 사용한다.
- 한 레벨에서는 하나의 필드만 사용한다.
- 총 k개의 필드를 사요하는 검색이라면, k개의 레벨을 내려가면 검색에 사용하는 필드가 일치한다.
- h-1번째에서 마지막 필드로 분기했다면 h에서는 다시 첫번째 필드로 사용
- 2차원 KD-Tree
1레벨 : x축 비교 -> 2레벨 : y축 비교 -> 3레벨 : x축 비교 -> 4레벨 : y축 비교 ...
- 만약 [10|60] 노드를 검색 하고자 한다면 다음과 같은 순서가 된다.
(1) 1레벨 x축(50)보다 작으므로(10) A의 왼쪽 자식으로 내려간다.
(2) 2레벨 y축(70)보다 작으므로(60) B의 왼쪽 자식으로 내려간다.
(3) 3레벨 x축(25)보다 작으므로(10) D의 왼쪽 자식으로 내려간다.
(4) 검색 완료
삭제 연산
'C 자료구조&알고리즘' 카테고리의 다른 글
| R-Tree (0) | 2023.04.18 |
|---|---|
| KDB-Tree (0) | 2023.04.18 |
| B-트리 (B-Tree) (0) | 2023.04.18 |
| 레드 블랙 트리(Red Black Tree) (0) | 2023.04.18 |
| 자가 균형 이진 탐색 트리(AVL 트리) (0) | 2023.04.18 |
