KDB 트리
-
KDB 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 30. 14:07
KDB 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KDB 트리는 노드의 키를 통해 분기하는 게 아니라 전체 영역을 쪼개가며 진행하게 된다. KDB 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 이때, k 차원의 키를 사용하는 영역 노드는 다음과 같이 표현된다. (, , ... , ) ※ KDB 트리의 모든 내부 노드는 영역 노드이며, 모든 리프 노드는 키 노드이다. KD 트리에서의 검색 KD 트리의 검색은 다음의 순서를 따른다. 루트 노드에서부터 검색하려는 키가 포함된 영역을 가지는 영역 노드를 따라 진행한다. 리프 노드에 도달한 경우 리프 노드에 검색하려는 키가 존재..