Boost Intrusive/binary search树

Question

我正在寻找一个Voronoi镶嵌算法（Fortune算法;一个不重要的任务本身，methinks）的二叉搜索树，所以当然，我想我会有一个看看Boost。

Boost拥有Intrusive头文件，它似乎包含丰富的BST（如AVL，Splay树和替罪羊树 - 哈哈，我必须确保那个名字！）一见钟情正是我所需要的。

1：我错过了什么，或者有没有办法直接访问树的根节点？

2： AVL树是否适用于Fortune算法海滩线结构？

该死的，我以为这会很容易。

更新：也许是更好地说明什么，我的目标是实现：我想实现抛物线搜索即是财富的算法，在检测到新的站点部分的一部分，我们需要找到抛物线直接在头顶上。我想我会从根开始遍历树，以找到正确的弧。

Answer 1

最后我实现了我自己的AVL树。 Voronoi算法的复杂性似乎要求它，并且无论如何，Boost版本都无法访问节点（如果我错了，请指出;这是可能的，因为Boost的含糊不清）。

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

我注意到push_back/push_front不会调用树重新排序。也许我错过了文档。

Answer 3

其实查找根比听起来容易。

首先，你必须写一个使用boost ::侵入像钩子平常的东西，等

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

如果你想查找任何的boost ::侵入一个节点，你必须使用find （）。 现在，find（）函数需要一个基本上检查$ a> b $或$ b < a $（非常像strcmp的布尔输出），的overloaded（）运算符，您希望此运算符在根节点因此它将返回根作为结果。这样做的一个方法是

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

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

然后使用find（）很简单：

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树状容器有一个根（）成员返回一个迭代根节点或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; 
}