kd-트리

kd-트리(다차원검색트리)는 이진 탐색 트리를 다차원 공간으로 확장한 것으로써

기본 구조와 알고리즘은 BST와 유사하지만 트리의 레벨 차원을 번갈아 가며 비교한다는

점이 다르다.

 

KD-트리

- 이진검색트리를 확장한 것으로 k개(k≥2)의 필드로 이루어지는 키를 사용

- 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다

 

 

KD-트리 삽입

 

 

A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60)

 

1. A(50, 50)이 루트 자리를 차지

2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다

3. C(80, 85)는 x값 80이 루트의 x값 50보다 크므로 오른쪽 자식이 된다

4. D(25, 20)는 먼저 x값 25가 루트의 x값 50보다 작으므로 루트의 왼쪽으로 가서 B(10, 70)를 만난다

    y값 20이 B의 y값 70보다 작으므로 B의 왼쪽 자식이 된다

5. E(40, 85)는 x값 40의 루트의 x값 50보다 작고, y보다 85가 B의 y값 70보다 크므로 B의 오른쪽 자식이 된다

6. F(70, 85)는 x값 70이 루트의 x값 50보다 크고, y값 85가 C의 y값 85와 같으므로 B의 오른쪽 자식이 되었다.

7. G(10, 60)는 x값 10이 루트의 x값 50보다 작고, y값 60이 B의 y값 70보다 작고,

    x값 10이 D의 x값 25보다 작으므로 D의 왼쪽 자식이 된다.

 

 

KD-트리 삭제

 

 

KD-트리 삭제

1. 자식이 없는 경우

 : 노드만 제거

2. 자식이 하나뿐인 경우

 : 자식이 둘인 경우와 같이 해결

 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동

3. 자식이 둘인 경우

 : 오른족 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드를 찾아서 이동

 

 

KDB-트리

 

 

KDB-트리의 노드의 종류

1. 영역 노드 : 복수 개의(영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드이다.

2. 키 노드 : 복수개의(키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드이다.

 

각 차원에서 범위가 주어지고 영역은 이들을 모두 만족하는 공간을 말한다.

 

KDB-트리의 키 검색

 : 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려가면 된다.

 

KDB-트리의 키 삽입

1. 삽입할 키가 속하는 리프 노드를 찾는다.

2. 해당 리프 노드가 키를 더 수용할 수 있는 공간이 있으면 (키, 페이지 번호) 쌍을 삽입하고 끝난다

3. 리프 노드가 키를 더이상 수용할 수 없을 경우, 형제 노드와 재분배할 수 있으면 재분배하고 작업은 끝난다.

4. 재분배가 불가능하면 리프 노드를 분할하여 두개로 만든다.

   → 이에 따라 부모 노드에 있던 한 영역이 두개로 나누어지므로(영역, 페이지 번호) 쌍이 하나 늘어난다.

   → 부모 노드가(영역, 페이지 번호)를 하나 더 수용할 공간이 있으면 작업은 끝이다.

   → 만일 부모 노드가 이것을 수용할 수 없으면 부모 노드를 분할 한다.

 

 

코드

#pragma once

#include <math.h>
#include <list>

using namespace std;

// k-D tree 클래스
// T - k-D tree 노드 위치의 데이터 형
// DIM - k-D tree 노드 위치의 차원(데이터 수)
template <class T, int DIM>
class CKdTree {
public:
    // 노드의 위치를 포함하는 하이퍼 큐브 구조체
    struct sHyperCube
    {
        // 하이퍼 큐브의 범위(low, high)
        T _low[DIM], _high[DIM];

        sHyperCube (const T low[DIM], const T high[DIM])
        {
            // 초기화
            memcpy (_low,  low,  DIM*sizeof(T));
            memcpy (_high, high, DIM*sizeof(T));
        }

        void extend (const T pos[DIM])
        {
            // 노드가 tree에 추가될 때, 이 노드의 위치를 하이퍼 큐브가 포함하도록 범위를 조절한다.
            // 즉, 노드의 위치가 하이퍼 큐브 바깥에 있다면 하이퍼 큐브를 노드의 위치까지 확장한다.
            for (int i=0; i<DIM; i++) {
                if (pos[i] < _low[i]) _low[i] = pos[i];
                if (pos[i] > _high[i]) _high[i] = pos[i];
            }
        }

        T distance (const T pos[DIM])
        {
            // 하이퍼 큐브의 표면에서 노드의 위치(pos)까지 떨어진 거리를 계산한다.
            // 만일 노드가 하이퍼 큐브 내에 존재한다면 거리는 0이다.
            T d = T(0);

            for (int i=0; i<DIM; i++) {
                if (pos[i] < _low[i]) {
                    T dx = _low[i] - pos[i];
                    d += dx*dx;
                }
                else if (pos[i] > _high[i]) {
                    T dx = _high[i] - pos[i];
                    d += dx*dx;
                }
            }
            return sqrt(d);
        }
    };

    struct sKdNode
    {
        T _pos[DIM];        // 노드의 위치
        void *_data;        // 노드가 가지는 추가적인 데이터
        sKdNode *_left;     // 노드의 왼쪽(작은 값)
        sKdNode *_right;    // 노드의 오른쪽(큰 값)

        sKdNode (const T pos[DIM], void *data)
            : _data(data), _left(NULL), _right(NULL)
        {
            memcpy (_pos, pos, DIM*sizeof (T));
        }

        ~sKdNode ()
        {
            if (_left)
                delete _left;
            if (_right) delete _right;
        }
    };

public:
    // k-차원의 tree를 생성한다.
    CKdTree () : _root(NULL), _cube(NULL) { }

    ~CKdTree ()
    {
        if (_root) delete _root;
        if (_cube) delete _cube;
    }

    // k-D tree에 하나의 노드를 추가한다.
    void insert (const T pos[DIM], void *data)
    {
        insert_i (_root, pos, data, 0);

        // 하이퍼 큐브가 만들어지지 않았다면 새로 만들고
        // 이미 만들어져 있다면 새로운 점을 포함하도록 확장한다.
        if (!_cube) _cube = new sHyperCube (pos, pos);
        else        _cube->extend (pos);
    }

    // 찾고자 하는 위치(pos)에서 가장 가까운(nearest neighbour) 하나의 노드를 찾는다.
    sKdNode *nn_search (const T pos[DIM])
    {
        if (!_cube || !_root) return NULL;

        // 하이퍼 큐브 복사, 임시로 사용할 큐브를 만든다.
        sHyperCube tmp (_cube->_low, _cube->_high);

        // 가장 가까운 노드를 저장할 변수, 우선 root를 설정해 둔다.
        _res_min_node = _root;
        _res_min_dist = distance (_root->_pos, pos);

        // _root 노드부터 NN(nearest neighbour)를 반복적으로 찾는다.
        nn_search_i (_root, pos, &tmp, 0);

        return _res_min_node;
    }

    // low와 high 범위 안에 포함되는 모든 점을 찾는다.
    list<sKdNode *> *range_search (const T low[DIM], const T high[DIM])
    {
        _res_node.clear ();

        range_search_i (_root, low, high, 0);

        return &_res_node;
    }

private:
    inline T distance (const T pos1[DIM], const T pos2[DIM])
    {
        // 두 점(pos1, pos2)간의 유클리디안 거리를 계산한다.
        T d = T(0);

        for (int i=0; i<DIM; i++) {
            T dx = pos1[i] - pos2[i];
            d += dx*dx;
        }
        return sqrt(d);
    }

    inline bool compare (const T low[DIM], const T high[DIM], const T pos[DIM])
    {
        // 위치(pos)가 low, high 영역에 들어오는지 검사한다.
        // 영역에 들어오면 true를 리턴한다.
        for (int i=0; i<DIM; ++i) {
            if (pos[i] < low[i] || high[i] < pos[i]) {
                return false;
            }
        }
        return true;
    }

    void insert_i (sKdNode *&node, const T pos[DIM], void *data, int dir)
    {
        // 하나의 노드를 tree에 추가하는 실제 구현,
        // 방법은 이진 트리와 유사하다.
        if (!node) {
            node = new sKdNode(pos, data);
        }
        else {
            if (pos[dir] < node->_pos[dir]) {
                insert_i (node->_left, pos, data, (dir + 1) % DIM);
            }
            else {
                insert_i (node->_right, pos, data, (dir + 1) % DIM);
            }
        }
    }

    void nn_search_i (sKdNode *node, const T pos[DIM], sHyperCube *_cube, int dir)
    {
        if (!node) return;

        // tree내의 노드의 위치(node->pos)와 찾는 위치(pos)를 비교하여 노드의 어느 쪽을 먼저 탐색할 지를 결정한다.
        T dp = pos[dir] - node->_pos[dir];
        if (dp <= 0) {
            // 찾는 위치(pos)가 노드의 왼쪽에 있기때문에 왼쪽 노드를 먼저 탐색한다.

            // 하이퍼 큐브를 node->_pos[dir]위치를 기준으로 반으로 나누어
            // 나누어진 왼쪽 하이퍼 큐브로 노드의 왼쪽을 탐색해 나간다.
            T tmp = _cube->_high[dir];
            _cube->_high[dir] = node->_pos[dir];
            nn_search_i (node->_left, pos, _cube, (dir + 1) % DIM);
            _cube->_high[dir] = tmp;
        }
        else {
            // 하이퍼 큐브를 node->_pos[dir]위치를 기준으로 반으로 나누어
            // 나누어진 오른쪽 하이퍼 큐브로 노드의 오른을 탐색해 나간다.
            T tmp = _cube->_low[dir];
            _cube->_low[dir] = node->_pos[dir];
            nn_search_i (node->_right, pos, _cube, (dir + 1) % DIM);
            _cube->_low[dir] = tmp;
        }

        // 현재 노드의 위치와 찾는 위치(pos)간의 거리를 계산하여 이 값을 지금까지의 최소 거리 값과 비교한다.
        // 만일, 더 가깝다면 최소 거리와 노드의 포인터를 업데이트 한다.
        T d = distance (node->_pos, pos);
        if (d < _res_min_dist) {
            _res_min_node = node;
            _res_min_dist = d;
        }

        if (dp <= 0) {
            // dp <= 0인 경우, 위에서 왼쪽 노드를 먼저 탐색했기때문에 이제 오른쪽 노드도 탐색한다.

            T tmp = _cube->_low[dir];
            _cube->_low[dir] = node->_pos[dir];

            // 찾는 위치(pos)와 하이퍼 큐브간의 떨어진 거리를 계산해서 지금까지 찾은 최소 거리보다 길다면,
            // 이 노드의 아래에 있는 tree는 더이상 탐색하지 않아도 된다.
            if (_cube->distance (pos) < _res_min_dist) {
                nn_search_i (node->_right, pos, _cube, (dir + 1) % DIM);
            }
            _cube->_low[dir] = tmp;
        }
        else {
            T tmp = _cube->_high[dir];
            _cube->_high[dir] = node->_pos[dir];
            if (_cube->distance (pos) < _res_min_dist) {
                nn_search_i (node->_left, pos, _cube, (dir + 1) % DIM);
            }
            _cube->_high[dir] = tmp;
        }
    }

    void range_search_i (sKdNode *node, const T low[DIM], const T high[DIM], int dir)
    {
        if (!node) return;

        // 현재 노드의 위치가 찾는 범위(low, hight)안에 들어오면 이 노드를 찾은 결과에 저장한다.
        if (compare (low, high, node->_pos)) {
            _res_node.push_back (node);
        }

        // 노드의 위치가 찾는 범위(low, hight)에 걸쳐 있으면 sub-tree로 찾아들어간다.
        if (low[dir] <= node->_pos[dir]) {
            range_search_i (node->_left, low, high, (dir + 1) % DIM);
        }
        if (node->_pos[dir] <= high[dir]) {
            range_search_i (node->_right, low, high, (dir + 1) % DIM);
        }
    }

private:
    sKdNode *_root;
    sHyperCube *_cube;

    // range search 결과를 저장하는 곳
    list<sKdNode *> _res_node;

    // nearest neighbour search 결과를 저장하는 곳
    sKdNode *_res_min_node;
    T    _res_min_dist;
};