KD-Tree ( K-Dimensional Tree )

KD-Tree

• 다차원 공간에서의 데이터를 저장하고, Knn이나 range search와 같은 작업을 빠르게 하기 위한 공간 분할 기반의 자료구조다.
• 기본 구조
  • KD-Tree는 일종의 '이진 탐색 트리 Binary Search Tree'이다.
    • 1. 각각의 노드는 하나의 데이터를 저장한다.
    • 2.트리를 구축할때는 하나의 축(x,y,z,...차원)을 기준으로 데이터를 둘로 나눈다.
    • 3. 루트부터 내려갈때마다, 축을 번갈아 가며 나눈다.
    • ex) 루트는 x축을 기준으로 분할한다면, 루트의 자식은 y축을 기준으로 분할.
      그 다음 자식은 x축 기준, 그 다음은 y축 기준... 이러한 방식으로 반복한다.
• KD-Tree 생성 방법 ( 구축 과정 )
  • 1. 모든 포인트를 수집한다.
  • 2. 현재 차원( depth에 따라 바뀜 , depth % k )을 기준으로 포인트를 정렬한다.
  • 3. 정렬된 리스트의 중간값을 루트로 선택한다.
  • 4. 왼쪽 절반은 왼쪽 서브트리 , 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 나눈다.
  • ==> 위와 같은 과정으로, KD-Tree는 log( n ) 깊이를 가지는 트리가 된다.
• KD-Tree의 탐색 방법 ( 최근접 이웃 찾기 예시 )
  • 1. 현재 노드를 방문
  • 2. 목표 포인트가 속하는 방향( right / left )으로 먼저 내려간다.
  • 3. 리프 노드까지 내려가면서 후보를 확장
  • 4. 백트래킹 하면서, 다른 방향에도 더 가까운 점이 있을 가능성이 있다면, 반대방향도 탐색
  • 5. 가장 가까운 점을 반환 
• 장점
  • 다차원 검색이 빠르며, 공간 분할이 직관적이다.
• 단점
  • 차원이 커지면 성능이 급감하며, 데이터가 동적으로 변할때 트리 재구성이 복잡하다.