Boost入侵/二进制搜索树

Question

我在为Voronoi算法寻找二叉树(“财富”的算法，这本身就是一项相当重要的任务)，所以，我想我应该看看Boost。

Boost有一个Intrusive头文件，它似乎包含大量的BST(例如AVL、Splay树和替罪羊树--哈哈，我必须确定这个名字！)乍一看，这正是我所需要的。

1:是我遗漏了什么，还是没有办法直接访问树的根节点？

2:是一种适合于财富算法海滩线结构的AVL树？

妈的，我以为这会很容易。

更新：也许更好地说明我的目标:我想实现抛物线搜索，这是“财富”算法的一部分，也就是检测到新站点的部分，我们需要直接查找抛物线。我想我应该从树根开始遍历这棵树，以便找到正确的弧线。

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_前沿不调用树的重新排序。也许我在医生里错过了。

Answer 3

实际上查找根比听起来容易。

首先，您必须编写常用的用于使用boost:侵扰性的东西，如钩子，等等。

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

如果您想要在任何boost：：In侵扰中查找节点，则必须使用find()。现在，find()函数需要一个重载()操作符，它基本上检查$a>b$或$b是否<$(非常像strcmp的布尔输出)，您希望这个操作符在根节点处失败，因此它将返回根作为结果。这样做的一种方法就是

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
    }