검색트리 [KD-트리, KDB-트리]

http://blog.naver.com/pluulove84/100058770623

다차원검색트리

 

KD-트리

- 이진검색트리를 확장한 것으로 k개(k≥2)의 필드로 이루어지는 키를 사용

- 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다

 

 

KD-트리 삽입

 

 

A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60)

 

1. A(50, 50)이 루트 자리를 차지

2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다

3. C(80, 85)는 x값 80이 루트의 x값 50보다 크므로 오른쪽 자식이 된다

4. D(25, 20)는 먼저 x값 25가 루트의 x값 50보다 작으므로 루트의 왼쪽으로 가서 B(10, 70)를 만난다

    y값 20이 B의 y값 70보다 작으므로 B의 왼쪽 자식이 된다

5. E(40, 85)는 x값 40의 루트의 x값 50보다 작고, y보다 85가 B의 y값 70보다 크므로 B의 오른쪽 자식이 된다

6. F(70, 85)는 x값 70이 루트의 x값 50보다 크고, y값 85가 C의 y값 85와 같으므로 B의 오른쪽 자식이 되었다.

7. G(10, 60)는 x값 10이 루트의 x값 50보다 작고, y값 60이 B의 y값 70보다 작고,

    x값 10이 D의 x값 25보다 작으므로 D의 왼쪽 자식이 된다.

 

 

KD-트리 삭제

 

 

KD-트리 삭제

1. 자식이 없는 경우

 : 노드만 제거

2. 자식이 하나뿐인 경우

 : 자식이 둘인 경우와 같이 해결

 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동

3. 자식이 둘인 경우

 : 오른족 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드를 찾아서 이동

 

 

KDB-트리

 

 

KDB-트리의 노드의 종류

1. 영역 노드 : 복수 개의(영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드이다.

2. 키 노드 : 복수개의(키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드이다.

 

각 차원에서 범위가 주어지고 영역은 이들을 모두 만족하는 공간을 말한다.

 

KDB-트리의 키 검색

 : 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려가면 된다.

 

KDB-트리의 키 삽입

1. 삽입할 키가 속하는 리프 노드를 찾는다.

2. 해당 리프 노드가 키를 더 수용할 수 있는 공간이 있으면 (키, 페이지 번호) 쌍을 삽입하고 끝난다

3. 리프 노드가 키를 더이상 수용할 수 없을 경우, 형제 노드와 재분배할 수 있으면 재분배하고 작업은 끝난다.

4. 재분배가 불가능하면 리프 노드를 분할하여 두개로 만든다.

   → 이에 따라 부모 노드에 있던 한 영역이 두개로 나누어지므로(영역, 페이지 번호) 쌍이 하나 늘어난다.

   → 부모 노드가(영역, 페이지 번호)를 하나 더 수용할 공간이 있으면 작업은 끝이다.

   → 만일 부모 노드가 이것을 수용할 수 없으면 부모 노드를 분할 한다.

[출처] 검색트리 [KD-트리, KDB-트리] |작성자 프루케이