침입 형/이진 검색 트리를 부스트

Question

나는 Voronoi tessellation 알고리즘 (Fortune의 알고리즘, 그 자체로는 단순하지 않은 태스크, methinks)에 대한 2 진 검색 트리를 찾고 있는데, 물론, 나는 부스트를보십시오.

부스트에는헤더 파일이 있습니다.이 파일에는 AVL, 스플레이 트리 및 희생양 나무와 같은 풍부한 BST가 포함되어있는 것으로 보입니다. 하, 그 이름을 꼭 확인해야했습니다. 내가 필요한 것 일 뿐이야.

1 : 내가 누락되었거나 나무의 루트 노드에 직접 액세스 할 수있는 방법이 없습니까?

2 : 포춘 알고리즘의 해변 선 구조에 적합한 AVL 트리가 있습니까?

젠장,이게 쉬운 일이라고 생각했습니다.

업데이트 : 아마도 그것은 내가 달성하기 위해 무엇을 목표로 명시하는 것이 좋습니다 : 나는 포춘 알고리즘, 새 사이트가 감지 부분의 일부입니다 포물선 검색을 구현하고 싶습니다 그리고 우리는을 찾아야 포물선이 바로 오버 헤드. 정확한 원호를 찾기 위해 뿌리부터 나무를 횡단 할 것이라고 생각했습니다.

Answer 1

결국 내 자신의 AVL 트리를 구현했습니다. 보로 노이 (Boronoi) 알고리즘의 복잡성으로 인해이를 요구하는 것처럼 보였고, 부스트 버전은 어쨌든 노드에 액세스 할 수 없었습니다 (실수라고 생각하면 부스트가 불분명 할 수도 있음).

AVL 트리가 제대로 작동하는 것 같습니다.

Answer 2

iterator begin(); 
const_iterator begin() const; 
const_iterator cbegin() const; 

문서를 기반으로 조금 명확하지 않지만 begin()은 첫 번째 헤더 노드 (루트 노드라고도 함)를 반환합니다.

http://www.dcs.gla.ac.uk/~samm/trees.html

업데이트

#include <iostream> 
#include <algorithm> 
#include <boost/intrusive/rbtree.hpp> 

using namespace boost::intrusive; 

struct X : public set_base_hook<optimize_size<true> > { 
    X(int x) : _x{x} { } 

    int _x; 

    friend inline std::ostream& operator<<(std::ostream&, const X&); 
    friend bool operator<(const X&, const X&); 
    friend bool operator>(const X&, const X&); 
    friend bool operator==(const X&, const X&); 
}; 

std::ostream& operator<<(std::ostream& os, const X& x) { 
    os << x._x; 
    return os; 
} 

bool operator<(const X& lhs, const X& rhs) { return lhs._x < rhs._x; } 
bool operator>(const X& lhs, const X& rhs) { return lhs._x > rhs._x; } 
bool operator==(const X& lhs, const X& rhs) { return lhs._x == rhs._x; } 

int main() 
{ 
    typedef rbtree<X> tree_t; 

    tree_t tree; 
    X x0(0); 
    X x1(1); 
    X x2(2); 

    /*! Output is the same for the following 
    * X x1(1); 
    * X x0(0); 
    * X x2(2); 
    */ 

    tree.insert_unique(x1); 
    tree.insert_unique(x0); 
    tree.insert_unique(x2); 

    std::for_each(
      tree.begin(), tree.end(), 
      [](const X& xx) { std::cout << "x: " << xx << std::endl; }); 
} 

출력

X : 0 X : 1 X : 2

I push_back/push_front가 트리 재주문을 호출하지 않는다는 것을 알았습니다. 아마 나는 문서에서 그것을 놓쳤다.

Answer 3

사실 루트를 찾는 것이 소리보다 쉽습니다.

첫째, 당신은 등 부스트 :: 후크와 같은 관입 사용하는 보통의 물건을 쓸 필요가

당신이 어떤 부스트 :: 방해의 노드를 조회하려면, 당신은 찾을 사용해야

boost::intrusive::avltree<Object> avl; 

(). find() 함수는 기본적으로 $ a> b $ 또는 $ b < $ (strcmp의 부울 출력과 매우 유사)인지 확인하는 overloaded() 연산자가 필요합니다. 이 연산자는 루트에서 실패합니다. 노드 그래서 결과로 루트를 반환합니다.

int data=0; 
boost::intrusive::avltree<Object>::iterator it = avl.find(data, RootComp()); 
    if(it != avl.end()){ 
     //*it is the root 
    }else{ 
     // the tree is empty 
    } 

Answer 4

Boost.Intrusive 나무와 같은 용기가 루트 노드에 반복자를 반환하는 루트() 멤버를 가지고이 일을하는 한 가지 방법은

다음

class RootComp{ 
bool operator() (const Object &a, const int b) const { 
     return false; 
    } 

    bool operator() (int b, const Object &a) const{ 
     return false; 
    } 
}; 

찾기 (사용)이 간단 할 것 또는 루트 노드가없는 경우 end(). 그 기능들은 오래 전부터 저질러졌다.

https://github.com/boostorg/intrusive/commit/6d38384e369697894bb71fb81132ad60b796c70c

그 기능을 문서화, 그래서 그들은 지금 공식과 같습니다 커밋 다음. 다음 코드는이를 사용하는 방법을 보여줍니다 :

#include <boost/intrusive/set.hpp> 
#include <cassert> 

using namespace boost::intrusive; 

struct MyClass : public set_base_hook<> 
{ 
    friend bool operator<(const MyClass&, const MyClass&) 
    { return true; } 
}; 

int main() 
{ 
    set<MyClass> set; 
    //end() is returned when the tree is empty 
    assert(set.root() == set.end()); 

    //insert myobject, must be root 
    MyClass myobject; 
    set.insert(myobject); 
    assert(&*set.root() == &myobject); 

    //erase and check root is again end() 
    set.erase(set.root()); 
    assert(set.croot() == set.cend()); 

    return 0; 
}