Accessing left child or right child of a node in a

问题:

I know that std::set is a balanced tree, and standard C++ forbids accessing the children of a node in std::set, But I was wondering if one can access the children and parent of a node in an avl_set in boost library. If its not possible, Is there any reliable libraries like boost that contains self balanced trees that allows such actions?

回答1:

Yes, boost contains an avl tree implementation (and some variants of it, IIRC).

• http://www.boost.org/doc/libs/1_58_0/doc/html/intrusive/avl_set_multiset.html#intrusive.avl_set_multiset.avl_set_multiset_hooks

That is part of of the Boost Intrusive library. The semantics of this library can be a bit unusual if you're used to regular (standard library) containers.

In fact the library comes with many competing tree algorithms, that you can switch by selecting a different template argument type. See http://www.boost.org/doc/libs/1_58_0/doc/html/intrusive/node_algorithms.html

---

Also note that Intrusive Containers are - by there very nature - very open. You can inspect the node hooks, or, in fact, replace them with your custom value traits which brings the pointer layout completely under your control.