c++ - 什么是好的稳定的 C++ 树实现？

Question

我想知道是否有人可以推荐一个好的 C++ 树实现，如果可能的话，希望它是兼容 stl 的。

作为记录，我以前写过很多次树算法，我知道这很有趣，但如果可能的话，我想变得务实和懒惰。因此，与工作解决方案的实际链接是这里的目标。

注意：我正在寻找通用树，而不是平衡树或地图/集，在这种情况下，结构本身和树的连接性很重要，而不仅仅是其中的数据。所以每个分支都需要能够保存任意数量的数据，并且每个分支都应该是可单独迭代的。

Answer 1

我不知道您的要求，但是如果您主要对结构感兴趣，而不是对特定于树的好处（例如通过平衡的速度）感兴趣，那么使用图表（例如在Boost Graph中的实现）会不会更好? 您可以通过图表“模拟”一棵树，也许它会（从概念上）更接近您正在寻找的东西。

Answer 2

看看这个。

C++ 的 tree.hh 库为 n 叉树提供了一个类似 STL 的容器类，模板化了存储在节点上的数据。提供了各种类型的迭代器（post-order、pre-order 等）。在可能的情况下，访问方法与 STL 兼容，或者可以使用替代算法。

高温高压

Answer 3

我将建议使用 std::map 而不是树。

树的复杂性特征是：

插入：O(ln(n))
删除：O(ln(n))
查找：O(ln(n))

这些与 std::map 保证的特征相同。
因此，std::map 的大多数实现都在底层使用了树（红黑树）（尽管从技术上讲这不是必需的）。

Answer 4

如果您没有 (key, value) 对，而只是键，请使用 std::set。它使用与 std::map 相同的红黑树。

Answer 5

好的，伙计们，我找到了另一个树库；stlplus.ntree。但是还没试过。

Answer 6

假设问题是关于平衡的（以某种形式，主要是红黑树）二叉树，即使情况并非如此。

平衡二叉树，如向量，允许管理一些元素的排序，而不需要任何键（比如通过在向量中的任何位置插入元素），但是：

• 对一个元素的所有修改具有最佳 O(log(n)) 或更好的复杂性（在任何迭代器的开始、结束和前后添加/删除）
• 除了直接破坏迭代器指向的元素之外，通过任何修改来保持迭代器。

可选地，可以支持像向量中的索引访问（按元素计算一个 size_t 的成本），复杂度为 O(log(n))。如果使用，迭代器将是随机的。

可选的顺序可以通过一些比较函数来强制执行，但迭代器的持久性允许使用不可重复的比较方案（例如：交通堵塞期间任意车道改变）。

在实践中，平衡二叉树具有向量、列表、双链表、map、multimap、deque、queue、priority_queue 的接口......对于所有单元素操作都达到了理论上的最优 O(log(n)) 复杂度。

<sarcastic> 这大概就是为什么 c++ stl 没有提出它的原因</sarcastic>

由于难以正确管理平衡，特别是在元素提取期间，个人可能无法自行实现一般平衡树。

平衡二叉树没有广泛可用的实现，因为最先进的红黑树（此时由于移除期间固定数量的昂贵树重组而成为最佳平衡树类型）知道实现，每个实现者都从结构发明者的初始代码不允许迭代器持久性。这可能是缺少全功能树模板的原因。