KdTree

UserPreferences

1. 개요
2. 샘플
3. 링크
4. 다운로드

1 개요

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

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

2 샘플

헤더 파일은 알아서...



//////////////////////////////////////////////////////////////////////////////
/// \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;

}

3 링크

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

4 다운로드

• An intoductory tutorial on kd-trees (PDF)
  

• CategoryAlgorithm