[Algorithm Part 1] 8. kd tree (multi-dim data)

BST를 이용하면, range search, range count 연산을 평균적으로 $\log N$시간 안에 수행할 수 있다.

하지만, 이는 1차원 데이터일 때만 가능했다. 

 

다차원 데이터의 range 연산을 수행하는 방법에는 여러 가지가 있다.

1. Scan: 모든 데이터를 비교해 한다. (연산 비용이 비싸다.)
2. Grid: 벡터 공간을 $M^2$개 작은 공간으로 나누고, 탐색 범위와 겹치는 공간만 비교한다. (clustering된 데이터에 취약)

이번 글에서는, 다차원 데이터의 range search (or count) 연산을 효율적으로 처리해주는 kd 트리에 대해 살펴볼 것이다.

---

kd 트리는 (BST를 확장한 개념으로) 자료 구조(data structure)는 같지만, 노드에 다른 제약 조건(or 의미 부여)을 걸어주었다.

(BST: 노드는 왼쪽 노드보다 커야 하고, 오른쪽 노드보다 작아야 한다.)

Definition of kd tree

kd 트리는 이진 트리이며, 다음과 같은 조건을 만족하는 노드를 가지고 있다.

노드는 $x_1(=x), x_2(=y), \cdots, x_k$개의 key가지고 있다. ($k$차원을 표현하기 위해)

깊이가 $i-1$인 노드는

1. 왼쪽 서브 트리의 모든 노드보다 $i \mod k$번째 죄표값($i$th coordinate value)이 커야 한다. 
2. 오른쪽 서브 트리의 모든 노드보다 $i \mod k$번째 좌표값($i$th coordinate value)이 작아야 한다.

예를 들어, 2차원 데이터를 가지고 있는 노드라면,

노드는 (x-coordinate value, y-coordinate value)로 구성되어 있으며,

level-0 노드(root)는 왼쪽 노드보다 $x$값이 커야 하고, 오른쪽 노드보다 $x$값이 작아야 한다.

level-1 노드는 왼쪽 노드보다 $y$값이 커야 하고, 오른쪽 노드보다 $y$값이 작아야 한다.

깊이가 내려가면서 기준이 바뀐다. (level-2n = $x$ value, level-(2n+1)= $y$ value)

Data Structure

노드 key가 $k$개인, BST를 사용한다.

Operations

search range

1. root 노드가 탐색 범위에 있는지 확인한다.
2. 노드와 탐색 범위를 비교해, 각 서브 트리가 탐색 범위에 있는지 확인한다.
3. 왼쪽 서브 트리가 탐색 범위에 있으면, 재귀적으로 왼쪽 서브 트리를 탐색한다.
4. 오른쪽 서브 트리가 탐색 범위에 있으면, 재귀적으로 오른쪽 서브 트리를 탐색한다.

Performance

	range search
	typical case	worst case
kd-tree	$R + \log N$	$R + \sqrt N$