c++ - 访问 avl_set 中节点的左子节点或右子节点

Question

我知道 std::set 是一棵平衡树，标准 C++ 禁止访问 std::set 中节点的子节点，但我想知道是否可以在 boost 库的 avl_set 中访问节点的子节点和父节点。如果不可能，是否有像 boost 这样包含允许此类操作的自平衡树的可靠库？

Answer 1

是的，boost 包含一个 avl 树实现(以及它的一些变体，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

那是 Boost Intrusive 库的一部分。如果您习惯使用常规(标准库)容器，则此库的语义可能有点不寻常。

事实上，该库带有许多相互竞争的树算法，您可以通过选择不同的模板参数类型来进行切换。参见 http://www.boost.org/doc/libs/1_58_0/doc/html/intrusive/node_algorithms.html

---

另请注意，侵入式容器本质上是非常开放的。您可以检查节点 Hook ，或者实际上，将它们替换为您的 custom value traits这使指针布局完全在您的控制之下。