KD-Tree (\(k\)-Dimensional Tree)
KD-트리 (\(k\)-차원 트리)
* 검색 트리의 종류 (URL)
- KD-Tree는 Binary Search Tree를 확장한 개념으로,
\(k\)개(\(k \geq 2\))의 Field로 이루어진 Key를 연산에 사용한다.
Mechanism (원리)
Branch on KD-Tree
- KD-Tree에서 분기는
Level=0인 Node(=Root Node)는 첫 번째 Field를 이용해 분기하고,
Level=1인 Node는 두 번째 Field를,
Level=2인 Node는 세 번째 Field를 이용해 분기하는 방식으로 이루어진다.
(즉, 동일한 Level에 있는 Node들은 같은 순서에 있는 Field를 이용해 분기한다.)
※ KD-Tree에서 \(\mathrm{Level} \; = \; i\)에 있는 Node들은 \(i(mod k)번째 Field에 위치한 Key값만을 이용하여 분기한다.
- \(h-1\)번째 Level에서 마지막 Field를 이용하여 분기했다면,
그 다음 Level(\(h\)번째)에서는 다시, 첫 번째 Field를 이용하여 분기한다.
- 즉, 분기에 필요한 Field는 \(i \; \mathrm{mod} \; k\)번째 Field인 것이다.
(\(i\)는 Node가 위치한 Level 값이다.)
Space Division
 |
| [Given KD-Tree] - 주어진 KD-Tree가 위와 같다 하자. - Empty Tree에서 부터, 노드 A, B, C, D, E, F, G가 차례대로 삽입되었다. (각 Level에서 분기에 쓰이는 Key가 달라진다는 점만 추가적으로 고려하면, Binary Search Tree와 삽입 측면에서 다를 바가 없다.) |
 |
| [Memory Space Division by KD-Tree] - 위 Kd-Tree의 노드들에 의해 분할되는 메모리 공간을 위와 같은 그림으로 표현할 수 있다. - k개의 Field를 가진 노드들로 구성된 KD-Tree는 k차원의 공간을 분할한다. (위 예시에서는 2개의 Field를 가지므로, 2차원 공간을 분할하게 된다.) - KD-Tree에서 각각의 노드들은 k차원 공간의 한 점에 해당된다. - KD-Tree의 한 노드에서 Field x를 사용해 분기하는 것은, 해당 노드가 속한 k차원 공간에서 x의 차원에 대해 공간을 둘로 분할하는 효과를 낸다. - KD-Tree에서의 검색은 k차원 공간에서 나누어진 결과에 따라 해당 노드가 속한 공간의 범위를 점점 좁혀나가는 연산이다. |
Query Operation (검색 연산)
- 기본적으로, Binary Search Tree에서의 검색 연산과 같다.
- 검색하고자 하는 노드의 Key값을 기준으로,
Root부터 시작하여 해당 Level에서 비교하기로 정한 Key값과 비교하여 분기 여부를 결정짓는다.
Insertion Operation (삽입 연산)
- 기본적으로, Binary Search Tree에서의 삽입 연산과 같다.
- 검색하듯, 트리를 따라 내려가다 Leaf Node를 만나면,
Key값을 기준으로 왼쪽 Child에 삽입할 지, 오른쪽 Child에 삽입할 지를 결정한다.
Deletion Operation (삭제 연산)
- KD-Tree에서는 하나의 노드가 최대 2개의 Child를 가질 수 있으며,
보유한 Child 개수에 따른 삭제 방법은 아래와 같다.
1) # of Child = 0
- 제거 대상 노드를 그냥 제거하면 된다.
(Child가 없으므로, 신경쓸게 없다.)
2) # of Child = 1
- (3)번의 2개의 Child를 가질 때와 같은 방법으로 처리한다.
- 오른쪽 자식만 있을 경우, 오른쪽 Subtree에 있는 노드들 중 제거 대상 노드의 Field값이 가장 작은 노드를 떼어다
제거 대상 노드의 위치에 놓는다.
- 왼쪽 자식만 있을 경우, 왼쪽 Subtree에 있는 노드들 중 제거 대상 노드의 Field값이 가장 큰 노드를 떼어다
제거 대상 노드의 위치에 놓는다.
3) # of Child = 2
- 제거 대상 노드의 오른쪽 Subtree에 있는 노드들 중,
제거 대상 노드가 사용하는 Field값이 가장 작은 노드를 떼어다, 제거 대상 노드의 위치에 갖다 놓는다.
- 새롭게 위치된 노드가 Child를 갖고 있는 경우, 이 노드를 대체할 노드를 Recursive하게 찾는다.
Example. KD-Tree Deletion Operation
| 1) Given KD-Tree |
 |
| - 주어진 KD-Tree가 위와 같다 하자. - 각각의 Level에서 활성화 된 Field는 파란색, 녹색으로 색칠되어 있다. |
| 2) Delete Node A |
 |
| - 노드 A를 KD-Tree에서 제거하고자 한다. - 노드 A는 Root이기도 하며, 두 개의 Child를 갖고 있다. (즉, 오른쪽 Subtree내에서 첫 번째 Field값이 가장 작은 노드를 찾아야 한다.) |
| 3) Detect Substitution |
 |
| - 제거 대상인 노드 A의 오른쪽 Subtree중, 첫 번째 Field 값이 가장 작은 노드는 C이다. - 즉, C를 A자리에 위치시키게 된다. |
| 4) Remove A & Relocating C |
 |
| - 노드 C를 노드 A의 자리에 위치시키고, 노드 A는 삭제한다. - 이렇게 되면, 원래 노드 C가 위치해있던 자리에 공석이 생긴다. (이는 노드 C가 제거된 것과 같으므로, 노드 C를 제거한다는 관점으로 접근한다.) - 즉, 노드 C에 대한 제거를 Recursive하게 처리해야 한다. |
| 5) Remove C |
 |
| - 노드 C를 제거한다는 관점으로 트리를 수리한다. - 노드 C는 두 개의 Child를 갖고 있으므로, 노드 C의 오른쪽 Subtree에서 두 번째 Field(=노드 C의 활성화 필드)값 중 가장 작은 값을 가진 노드(=Node L)를 노드 C의 자리에 재배치한다. |
| 6) Relocating L |
 |
| - 노드 L은 원래 Child가 없던 노드이므로, 노드 L의 공석에 대한 처리는 따로 필요로하지 않는다. - 즉, 노드 A의 제거가 완료되었다. |
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
