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

What's a good and stable C++ tree implementation?

提问by Robert Gould

I'm wondering if anyone can recommend a good C++ tree implementation, hopefully one that is stl compatible if at all possible.

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

For the record, I've written tree algorithms many times before, and I know it can be fun, but I want to be pragmatic and lazy if at all possible. So an actual link to a working solution is the goal here.

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

Note: I'm looking for a generic tree, not a balanced tree or a map/set, the structure itself and the connectivity of the tree is important in this case, not only the data within. So each branch needs to be able to hold arbitrary amounts of data, and each branch should be separately iterateable.

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

采纳答案by Roel

I don't know about your requirements, but wouldn't you be better off with a graph (implementations for example in Boost Graph) if you're interested mostly in the structure and not so much in tree-specific benefits like speed through balancing? You can 'emulate' a tree through a graph, and maybe it'll be (conceptually) closer to what you're looking for.

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

回答by MvdD

Take a look at this.

看看这个。

The tree.hh library for C++ provides an STL-like container class for n-ary trees, templated over the data stored at the nodes. Various types of iterators are provided (post-order, pre-order, and others). Where possible the access methods are compatible with the STL or alternative algorithms are available.

C++ 的 tree.hh 库为 n 元树提供了一个类似于 STL 的容器类，对存储在节点上的数据进行了模板化。提供了各种类型的迭代器（后序、前序等）。在可能的情况下，访问方法与 STL 兼容或可用的替代算法。

HTH

HTH

回答by Martin York

I am going to suggest using std::map instead of a tree.

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

The complexity characteristics of a tree are:

一棵树的复杂性特征是：

Insert:       O(ln(n))
Removal:  O(ln(n))
Find:         O(ln(n))

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

These are the same characteristics the std::map guarantees.
Thus as a result most implementations of std::map use a tree (Red-Black Tree) underneath the covers (though technically this is not required).

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

回答by Denes Tarjan

If you don't have (key, value) pairs, but simply keys, use std::set. That uses the same Red-Black tree as std::map.

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

回答by Robert Gould

Ok folks, I found another tree library; stlplus.ntree. But haven't tried it out yet.

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

回答by alta

Let suppose the question is about balanced (in some form, mostly red black tree) binary trees, even if it is not the case.

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

Balanced binaries trees, like vector, allow to manage some ordering of elements without any need of key (like by inserting elements anywhere in vector), but :

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

• With optimal O(log(n)) or better complexity for all the modification of one element (add/remove at begin, end andbefore & after any iterator)
• With persistanceof iterators thru any modifications except direct destruction of the element pointed by the iterator.

• 对一个元素的所有修改使用最优 O(log(n)) 或更好的复杂性（在开始、结束和任何迭代器之前和之后添加/删除）
• 与持久性的迭代器通除了由迭代指向的元件的直接破坏任何修改。

Optionally one may support access by index like in vector (with a cost of one size_t by element), with O(log(n)) complexity. If used, iterators will be random.

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

Optionally order can be enforced by some comparison func, but persistence of iterators allow to use non repeatable comparison scheme (ex: arbitrary car lanes change during traffic jam).

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

In practice, balanced binary tree have interface of vector, list, double linked list, map, multimap, deque, queue, priority_queue... with attaining theoretic optimal O(log(n)) complexity for all single element operations.

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

<sarcastic> this is probably why c++ stl does not propose it </sarcastic>

<sarcastic> 这可能就是为什么 c++ stl 不建议它 </sarcastic>

Individuals may not implement general balanced tree by themselves, due to the difficulties to get correct management of balancing, especially during element extraction.

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

There is no widely available implementation of balanced binary tree because the state of the art red black tree (at this time the best type of balanced tree due to fixed number of costly tree reorganizations during remove) know implementation, slavishly copied by every implementers' from the initial code of the structure inventor, does not allow iterator persistency. It is probably the reason of the absence of fully functionnal tree template.

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