KDTree1 SDBMS ⑥ The KD Tree SDBMS 공간데이터베이스 ⑥ The KD Tree 1. KD Tree : $k$-d tree, $k$-dimentional tree $k$차원의 점을 관리하는 이진 트리 구조이다. 트리의 모든 leaf는 $k$차원의 점이고 non-leaf는 공간을 나누는 hyperplane*이다. * 본래 공간보다 한 차원 하위의 공간이라고 생각하면 될 듯. 3차원이라면 평면, 2차원이라면 선분 등 기본적으로는 중앙값을 기준으로 점을 두 영역에 나누고, 또 중앙값을 기준으로 나누는 걸 반복해 leaf에 한 개의 점이 할당될 때까지 재귀적으로 트리를 빌드한다. 위 그림에서는 $x$를 기준으로 먼저 축을 골라 ①의 좌우로 점들을 나누고 다음 단계에서는 $y$를 기준으로 축을 골라 점을 나눴다. 다시 $x$, $y$, $x.. 2021. 4. 15. 이전 1 다음
