Boost Intrusive/binary search樹

我正在尋找一個Voronoi鑲嵌算法（Fortune算法;一個不重要的任務本身，methinks）的二叉搜索樹，所以當然，我想我會有一個看看Boost。Boost Intrusive/binary search樹

Boost擁有Intrusive頭文件，它似乎包含豐富的BST（如AVL，Splay樹和替罪羊樹 - 哈哈，我必須確保那個名字！）一見鍾情正是我所需要的。

1：我錯過了什麼，或者有沒有辦法直接訪問樹的根節點？

2： AVL樹是否適用於Fortune算法海灘線結構？

該死的，我以爲這會很容易。

更新：也許是更好地說明什麼，我的目標是實現：我想實現拋物線搜索即是財富的算法，在檢測到新的站點部分的一部分，我們需要找到拋物線直接在頭頂上。我想我會從根開始遍歷樹，以找到正確的弧。

來源

2013-05-22 Kristian D' Amato

最後我實現了我自己的AVL樹。 Voronoi算法的複雜性似乎要求它，並且無論如何，Boost版本都無法訪問節點（如果我錯了，請指出;這是可能的，因爲Boost的含糊不清）。

AVL樹似乎完美地完成了這項工作。

來源

2013-05-29 08:39:11

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-22 15:55:47

它似乎並不像它。調用'begin（）'似乎返回第一個元素，由比較函數決定。 –

感謝您的回覆，但仍然需要頂層（root/header）節點，而不是最左邊/最右邊的節點。 –

其實查找根比聽起來容易。

首先，你必須寫一個使用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 
    }

來源

2013-08-16 02:04:50

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

來源

2016-09-03 11:51:17 igaztanaga

Boost Intrusive/binary search樹

回答

相關問題