什么是一个好的和稳定的C++树实现？

Question

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

为了记录,我之前已经多次编写树算法,我知道它可以很有趣,但是如果可能的话,我想要务实和懒惰.因此,实际的工作解决方案链接就是目标.

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

Answer 1

我不知道你的要求,但如果你对结构感兴趣而不是树特定的好处,比如速度平衡,你不会更好地使用图形(例如Boost图中的实现) ？您可以通过图形"模拟"树,也许它(概念上)更接近您正在寻找的树.

Answer 2

看看这个.

用于C++的tree.hh库为n-ary树提供类似STL的容器类,模板化存储在节点上的数据.提供了各种类型的迭代器(下订单,预订等).在可能的情况下,访问方法与STL兼容,或者可以使用替代算法.

HTH

Answer 3

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

树的复杂性特征是:

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

这些是std :: map保证的相同特征.
因此,大多数std :: map的实现都使用了封面下的树(红黑树)(虽然从技术上讲这不是必需的).