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; }