4

我正在为 Voronoi 镶嵌算法（Fortune 的算法；我认为这本身就是一个该死的不平凡的任务）寻找二叉搜索树，所以当然，我想我会看看 Boost。

Boost 有Intrusive头文件，它似乎包含大量的 BST（例如 AVL、Splay 树和 Scapegoat 树 - 哈，我必须确定那个名字！）乍一看似乎正是我所需要的.

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

2： AVL树适合Fortune算法海滩线结构吗？

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

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

4

4 回答 4

3 
 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 不会调用树重新排序。也许我在文档中错过了这一点。

于 2013-05-22T15:55:47.197 回答
1

最后，我实现了自己的 AVL 树。Voronoi 算法的复杂性似乎需要它，并且 Boost 版本无论如何都无法访问节点（如果我弄错了，请指出；鉴于 Boost 的晦涩难懂，这是可能的）。

AVL 树似乎完美地完成了这项工作。

于 2013-05-29T08:39:11.237 回答
0

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

首先，您必须编写使用 boost::intrusive 的常用内容，如钩子等。

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

如果你想在任何 boost::intrusive 中查找一个节点，你必须使用 find()。现在，find() 函数需要一个重载的 () 运算符，它基本上检查 $a>b$ 或 $b < a$（非常类似于 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
    }
于 2013-08-16T02:04:50.210 回答
0

Boost.Intrusive 树状容器有一个 root() 成员，它返回一个迭代器到根节点，如果没有根节点，则返回 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;   
}
于 2016-09-03T11:51:17.853 回答