[알고리즘] 다차원 검색 트리

다차원 검색 트리 KD-트리

• 검색키가 두 개 이상의 필드로 이루어진 검색

• 3개의 다차원 검색트리와 하나의 다차원 저장/검색 방법 소개

– KD-트리

– KDB-트리

– R-트리

– 그리드 파일

KD-Tree

• 각 레벨에서 필드를 번갈아가며 검색에 사용한다

− 한 level에서는 하나의 필드만 사용한다

− 총 k개의 필드를 사용하는 검색이라면, k개의 level을 내려가면 검색에 사용하는 필드가 일치한다

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) 검색 완료

KD-Tree의 노드 삭제

[50|50] 노드를 삭제하기 위해 직후 노드를 찾는다. 1레벨은 x축이므로 직후 노드는 x축 값보다 큰 노드 중 가장 작은 노드가 된다

삭제할 노드를 대체한다. 대체하고 난 후 빈 자리를 채울 대체할 노드를 다시 채우기 위해 직후 노드를 찾는다.

2레벨은 y축이므로 직후 노드는 y축 값보다 큰 노드 중 가장 작은 노드가 된다

삭제할 노드를 대체한다.

삭제 완료

[예제]

1.빈 KD-tree에 다음 키들을 차례로 삽입하는 과정을 적으시오. (3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)

2. 위 키들이 삽입된 KD-tree에서 다음 키들을 차례로 삭제하는 과정을 적으시오. (3, 6), (17, 15), (13, 15)

 

 

 

자료참조 - 쉽게 배우는 알고리즘 · 관계 중심의 사고법 / 문병로