KDB 트리 알고리즘

  KDB 트리 

B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다.

 

KDB 트리는 노드의 키를 통해 분기하는 게 아니라 전체 영역을 쪼개가며 진행하게 된다.

 

KDB 트리에는 다음의 두 종류의 노드가 존재한다.

• 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드
• 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드

 

이때, k 차원의 키를 사용하는 영역 노드는 다음과 같이 표현된다.

 

(<min0, max0>, <min1, max1>, ... , <mink-1, maxk-1>)

 

※ KDB 트리의 모든 내부 노드는 영역 노드이며, 모든 리프 노드는 키 노드이다.

 

쉽게 배우는 알고리즘 KDB 트리 그림 5-26

 

KD 트리에서의 검색

KD 트리의 검색은 다음의 순서를 따른다.

1. 루트 노드에서부터 검색하려는 키가 포함된 영역을 가지는 영역 노드를 따라 진행한다.
2. 리프 노드에 도달한 경우 리프 노드에 검색하려는 키가 존재하는지 확인한다.
3. 키가 존재하는 경우 해당 페이지에서 정보를 가져오고 종료한다.
4. 키가 존재하지 않는 경우 키가 존재하지 않는 것으로 간주하고 종료한다.

 

쉽게 배우는 알고리즘 KDB 트리 그림 5-27

 

KDB 트리에서의 삽입과 삭제

KDB 트리의 삽입과 삭제는 B 트리와 동일한 방식으로 진행되나 리프 노드에서 오버 플로우 또는 언더 플로우가 발생했을 때 영역 노드가 영향을 받으며 영역의 모양이 변경되는 점이 다르다.

 

※ 분할 또는 병합이 될 때 문제가 됐던 영역의 기준을 부모 노드의 전체 영역으로 확장하여 처리한다.

 

쉽게 배우는 알고리즘 KDB 트리 그림 5-28

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘