kd-tree

친구의 블로그에서 글을 읽다가 문제 하나를 봤습니다.
x와 y좌표를 가진 N개의 점들이 있는데, 원점에 가까운 10개의 점을 무려 O(n) 시간으로 찾으라는 무지막지한 문제. 해결 자체는 kd-tree로 가능하지만, O(n) 이라면 kd-tree가 답은 아니겠군요. kd-tree 생성에만 O(n*log(n))이 걸린다던데. 설마 넌센스인가?
근데 시간 복잡도를 제외하면, 예전에 자료구조 혹은 알고리즘 시간에 교수님이 냈던 과제랑 같은거 같네요. 그 땐 무식하게 푼 기억이 어렴풋이 납니다.

kd-tree

컴퓨터 과학에서 kd-tree는 k-차원 공간에 있는 점들을 조직하기 위한 공간-분할 데이터 구조입니다. kd-tree는 다차원 공간 탐색 키를 사용하는 탐색과 같은 응용에 유용한 데이터 구조입니다.(예를 들어, 범위 검색과 근접 검색). kd-tree는 BSP tree의 특별한 경우입니다.

kd-tree는 모든 노드(Node)가 k-차원의 점인 이진 트리(Binary tree)입니다. 리프(Leaf)가 아닌 모든 노드는 공간을 두 개의 작은 공간들(Subspaces)로 나눈 분리 경계면(초평면, Hyperplane)을 만듭니다. 분리 경계면 왼쪽의 점들은 노드의 왼쪽 서브 트리(Sub-tree)를 나타내고, 오른쪽의 점들은 오른쪽 서브 트리를 나타냅니다. 분리 경계면의 방향은 다음의 방법에 의해 선택됩니다. 서브 트리에 의해 쪼개진 모든 노드는 k-차원들 중 하나와 연관 됩니다. 분리 경계면은 방향 벡터에 수직입니다. 예를 들면, 선택된 x축으로 나뉘어진다면, x값보다 작은 서브 트리의 모든 점들은 오른쪽에 나타나고, x값 보다 큰 값들은 오른쪽 서브 트리에 나타납니다.

출처: http://en.wikipedia.org/wiki/Kd_tree