N 차원의 공간에서 임의의 영역에 포함되는 점들을 효율적으로 찾기 위한 트리.

노드 추가와 검색은 상당히 빠르나, 삭제가 느리다. 즉 동적으로 움직이는 점들을 관리하는 데에는 적당하지 않다.

헤더 파일은 알아서…

//////////////////////////////////////////////////////////////////////////////
/// \class KdTree
/// \brief N 차원의 공간에서 임의의 영역에 포함되는 점들을 효율적으로 찾기 
/// 위한 트리 자료 구조
///
/// T         : 좌표를 나타내는 데 사용할 데이터의 타입 (e.g : int, float...)
/// DIMENSION : 차원의 수. 최소 1보다는 커야한다.
//////////////////////////////////////////////////////////////////////////////
 
template <class T, int DIMENSION>
class KdTree
{
private:
    /// 내부적으로 사용하는 노드
    struct NODE
    {
        T     data[DIMENSION]; ///< 실제 좌표
        NODE* left;            ///< 좌측 자식
        NODE* right;           ///< 우측 자식
 
 
        /// \brief 생성자
        /// \param value[DIMENSION] 
        NODE(const T value[DIMENSION]) 
            : left(NULL), right(NULL) 
        {
            memcpy(data, value, sizeof(T) * DIMENSION);
        }
 
        /// \brief 소멸자
        ~NODE()
        {
            SAFE_DELETE(left);
            SAFE_DELETE(right);
        }
    };
 
    NODE* m_pRoot; ///< 루트 노드
 
 
public:
    /// \brief 생성자
    KdTree() : m_pRoot(NULL) {}
 
    /// \brief 소멸자
    virtual ~KdTree() { SAFE_DELETE(m_pRoot); }
 
 
public:
    /// \brief 좌표값을 트리에다 집어넣는다.
    /// \param value[DIMENSION] 좌표값
    void insert(const T value[DIMENSION]) 
    { 
        insert(value, m_pRoot, 0);
    }
 
    /// \brief 특정 범위 안에 들어오는 점들을 출력한다.
    /// \param low[DIMENSION] 범위 최소값
    /// \param high[DIMENSION] 범위 최대값
    /// \return int 비교 연산의 횟수
    int search(const T low[DIMENSION], const T high[DIMENSION])
    {
        return search(low, high, m_pRoot, 0);
    }
 
 
private:
    /// \brief 좌표값을 트리에다 집어넣기 위해 내부적으로 사용하는 함수
    /// \param value[DIMENSION] 좌표값
    /// \param pParent 부모 노드
    /// \param level 비교할 축 인덱스
    void insert(const T value[DIMENSION], NODE*& pParent, int level)
    {
        if (pParent == NULL)
        {
            pParent = new NODE(value);
        }
        else if (value[level] < pParent->data[level])
        {
            insert(value, pParent->left, (level + 1) % DIMENSION);
        }
        else
        {
            insert(value, pParent->right, (level + 1) % DIMENSION);
        }
    }
 
    /// \brief 특정 범위 안에 들어오는 점들을 출력하기 위해 내부적으로 
    /// 사용하는 함수
    /// \param low[DIMENSION] 범위 최소값
    /// \param high[DIMENSION] 범위 최대값
    /// \param pParent 부모 노드
    /// \param level 비교할 축 인덱스
    /// \return int 비교 연산의 횟수
    int search(const T low[DIMENSION], const T high[DIMENSION], NODE* pParent, int level)
    {
        if (pParent == NULL) return 0;
 
        int comparison = 1;
 
        bool bSuitable = true;
        for (int i=0; i<DIMENSION; ++i)
        {
            if (pParent->data[i] < low[i] || high[i] < pParent->data[i])
            {
                bSuitable = false;
                break;
            }
        }
 
        if (bSuitable)
        {
            cout << "(";
 
            for (int i=0; i<DIMENSION; ++i)
            {
                cout << pParent->data[i];
                if (i != DIMENSION - 1) cout << ",";
            }
 
            cout << ")" << endl;
        }
 
        if (low[level] <= pParent->data[level])
            comparison += search(low, high, pParent->left, (level + 1) % DIMENSION);
 
        if (pParent->data[level] <= high[level])
            comparison += search(low, high, pParent->right, (level + 1) % DIMENSION);
 
        return comparison;
    }
};

void test( )
{
    KdTree<int, 3> t;
 
    for( int i = 0; i < 1000; i++ )
    {
        int it[3] = { i, i, i };
        t.insert(it);
    }
 
    int low[3] = { 10, 10, 10 };
    int high[3] = { 15, 15, 15 };
 
    cout << "=============================" << endl;
    int total = t.search(low, high);
 
    cout << "=============================" << endl;
    cout << "Total comparison: " << total << endl;
 
}

• KD Tree Demo
• Devon Strawn : Quick KD-Tree Tutorial
• KD Tree - Searching in N-dimensions, Part I