KDTree

 

개요

 K-D 트리 (K-Dimensional Tree라고도 함)는 각 노드의 데이터가 공간의 K 차원 포인트인 이진 검색 트리다. 즉, K 차원 공간의 점을 구성하기위한 공간 분할 구조이다. K-D 트리의 비 잎 노드(non-leaf node)는 공간을 두 부분으로 나눈다.
루트는 x- 정렬 된 평면을 가질 것이고, 루트의 자식들은 모두 y- 정렬 된 평면을 가질 것이고, 루트의 손자들은 모두 x- 정렬 된 평면들을 가질 것이며, 루트의 증손자들은 모두 y- 정렬 된 평면들을 가질 것이다.

그래서 이해가능한 적당한 이미지를 찾기 힘들었다.

보통은 위의 2차원의 kdtree 이미지들이 많이 보이지만 이를 일반 트리처럼 표현하면 아래처럼 된다.

아래 좌표랑 위의 그래프랑 비교해보면 쉬울듯하다.

삽입

 다른 검색 트리에 요소를 추가하는 것과 같은 방식으로 kd 트리에 새로운 점을 추가한다. 먼저 삽입할 점이 분할 평면의 "왼쪽"또는 "오른쪽"에 있는지 여부에 따라 루트에서 시작하여 왼쪽 또는 오른쪽 자식으로 이동하여 트리를 탐색한다. 자식이 위치해야하는 노드에 도달하면 노드의 분할 평면 중 어느쪽에 새 노드가 포함되어 있는지에 따라 새 노드를 리프 노드의 왼쪽 또는 오른쪽 자식으로 추가한다.
 

Node *insertRec(Node *root, int point[], unsigned depth) 
{ 
    if (root == NULL) 
       return newNode(point); 

    unsigned cd = depth % k; 
  
    if (point[cd] < (root->point[cd])) 
        root->left  = insertRec(root->left, point, depth + 1); 
    else
        root->right = insertRec(root->right, point, depth + 1); 
  
    return root; 
} 

Node* insert(Node *root, int point[]) 
{ 
    return insertRec(root, point, 0); 
}

삭제

 1) 현재 노드에 삭제할 포인트가 있는 경우

    i) 삭제할 노드가 리프 노드라면 단순히 삭제

    ii) 삭제할 노드의 자식이 NULL이 아닌 경우

       오른쪽 하위 트리에서 현재 노드의 최소 차원을 찾는다.
       노드를 위의 최소값으로 교체하고 오른쪽 하위 트리에서 최소값을 재귀적으로 삭제한다.

    iii) 삭제 될 노드가 자식이 NULL이 아닌 것으로 남겨진 경우

        왼쪽 하위 트리에서 현재 노드의 최소 차원을 찾는다.
        위의 최소값으로 노드를 교체하고 왼쪽 하위 트리에서 최소값을 재귀적으로 삭제한다.
        새로운 왼쪽 하위 트리를 현재 노드의 오른쪽 하위 노드로 만든다.

 

2) 현재에 삭제할 포인트가 없는 경우

  삭제할 노드가 현재 차원의 현재 노드보다 작은 경우 왼쪽 하위 트리에 대해 반복한다.
  오른쪽 하위 트리에 대해 다시 반복한다.

 

Node *deleteNodeRec(Node *root, int point[], int depth) 
{ 
    if (root == NULL) 
        return NULL; 
  
    int cd = depth % k; 
  
    if (arePointsSame(root->point, point)) 
    { 
        if (root->right != NULL) 
        { 
            Node *min = findMin(root->right, cd); 
            copyPoint(root->point, min->point); 
            root->right = deleteNodeRec(root->right, min->point, depth+1); 
        } 
        else if (root->left != NULL)
        { 
            Node *min = findMin(root->left, cd); 
            copyPoint(root->point, min->point); 
            root->right = deleteNodeRec(root->left, min->point, depth+1); 
        } 
        else
        { 
            delete root; 
            return NULL; 
        } 
        return root; 
    } 
    if (point[cd] < root->point[cd]) 
        root->left = deleteNodeRec(root->left, point, depth+1); 
    else
        root->right = deleteNodeRec(root->right, point, depth+1); 
    return root; 
} 
 Node* deleteNode(Node *root, int point[]) 
{ 
   return deleteNodeRec(root, point, 0); 
}​