如何在boost中訪問rbtree的根目錄

Question

Iv基於this示例實現了一個紅黑樹。但我不明白標題的含義，它是樹的根？根據描述：

頭節點不僅保持鏈接，而且鏈接到樹的最左邊的節點，啓用恆定時間begin（）和樹的最右邊節點，在與通用集合算法（set_union等）一起使用時啓用線性時間性能;

如何使用頭節點訪問我的樹的根？那是什麼複雜性？

Answer 1

Boost Intrusive的RBTree實現中的頭節點包含指向根，最左側和最右側節點的鏈接（請參閱here）。所以parent_是指向根節點的指針。

您可以使用基於的容器抽象該示例中顯示的「算法策略」。你會寫custom value traits，就像我在我以前的答案鏈接：Accessing left child or right child of a node in avl_set

這裏有一個簡單，獨立的示例，說明如何使用實際rbtree容器（不只是算法）建立在你的節點類型。

請注意，您仍然可以「鑽取」並獲取使用容器特徵的節點。

Live On Coliru

struct my_node 
{ 
    my_node(int i = 0) : 
     parent_(nullptr), 
     left_ (nullptr), 
     right_ (nullptr), 
     int_ (i) 
    { } 

    my_node *parent_, *left_, *right_; 
    int  color_; 
    //data members 
    int  int_; 

    bool operator<(my_node const& other) const { return int_ < other.int_; } 
}; 

//Define our own rbtree_node_traits 
struct my_rbtree_node_traits 
{ 
    typedef my_node         node; 
    typedef my_node *         node_ptr; 
    typedef const my_node *       const_node_ptr; 
    typedef int          color; 
    static node_ptr get_parent(const_node_ptr n)  { return n->parent_; } 
    static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } 
    static node_ptr get_left(const_node_ptr n)   { return n->left_;  } 
    static void set_left(node_ptr n, node_ptr left) { n->left_ = left;  } 
    static node_ptr get_right(const_node_ptr n)  { return n->right_; } 
    static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } 
    static color get_color(const_node_ptr n)   { return n->color_; } 
    static void set_color(node_ptr n, color c)   { n->color_ = c;  } 
    static color black()        { return color(0);  } 
    static color red()         { return color(1);  } 
}; 

#include <boost/intrusive/link_mode.hpp> 
namespace bi = boost::intrusive; 

struct my_value_traits 
{ 
    typedef my_rbtree_node_traits  node_traits; 
    typedef node_traits::node   value_type; 
    typedef node_traits::node_ptr  node_ptr; 
    typedef node_traits::const_node_ptr const_node_ptr; 
    typedef value_type*     pointer; 
    typedef value_type const*   const_pointer; 

    static const bi::link_mode_type link_mode = bi::link_mode_type::normal_link; 

    static node_ptr  to_node_ptr (value_type &value)  { return &value; } 
    static const_node_ptr to_node_ptr (const value_type &value) { return &value; } 
    static pointer  to_value_ptr (node_ptr n)    { return n;  } 
    static const_pointer to_value_ptr (const_node_ptr n)  { return n;  } 
}; 

#include <boost/intrusive/rbtree.hpp> 
using mytree = bi::rbtree<my_node, bi::value_traits<my_value_traits> >; 

#include <iostream> 
#include <vector> 

int main() { 
    std::vector<my_node> storage { {1}, {3}, {4}, {2}, {3}, }; 

    mytree container; 
    container.insert_equal(storage.begin(), storage.end()); 

    // NOW for the "have your cake and eat it too" moment: 
    for (my_node& n : container) { 
     std::cout << n.int_ 
      << " (parent: " << n.parent_ << ")" 
      << " (left: " << n.left_ << ")" 
      << " (right: " << n.right_ << ")" 
      << "\n"; 
    } 
} 

哪個打印（例如）：

1 (parent: 0xb01c40) (left: 0) (right: 0xb01c80) 
2 (parent: 0xb01c20) (left: 0) (right: 0) 
3 (parent: 0x7fff6da3f058) (left: 0xb01c20) (right: 0xb01c60) 
3 (parent: 0xb01c60) (left: 0) (right: 0) 
4 (parent: 0xb01c40) (left: 0xb01ca0) (right: 0) 

Answer 2

一個Boost.Intrusive樹的結構bstree_algorithms的文檔（http://www.boost.org/boost/intrusive/bstree_algorithms.hpp）中說明。 「header」節點也被解釋爲：

「在樹的頂部節點被專門使用，該節點的父指針指向樹的根，它的左指針指向樹中最左端的節點樹和右邊的指針，這個節點用來表示結束迭代器。「

所以，你可以使用訪問根節點：

root = rbtree_algorithms::get_parent(header); 

如果您使用的值的特徵構建自己的容器，如sehe解釋的，因爲承諾：

https://github.com/boostorg/intrusive/commit/bbb4f724d037a6ab5ee0d9bde292f0691564960c

樹基於容器的容器具有root（）函數，該函數返回一個迭代器到根節點（或end（），如果不存在的話）具有O（1）複雜度，這可能更易於使用：

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