为什么 C STL 不提供任何“树”容器？

Question

为什么 C++ STL 不提供任何“树”容器，而最好使用什么？

我想将对象的层次结构存储为树，而不是使用树作为性能增强…

原文由 Roddy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可能想要使用树有两个原因：

您想使用树状结构来反映问题：

为此，我们有 boost 图形库

或者您想要一个具有树状访问特性的容器为此我们有

• std::map （和 std::multimap ）
• std::set （和 std::multiset ）

基本上这两个容器的特性使得它们实际上必须使用树来实现（尽管这实际上不是必需的）。

另请参阅此问题： C 树实现

原文由 Martin York 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

问题是没有一种万能的解决方案。此外，树甚至没有万能的 接口。也就是说，甚至不清楚这种树数据结构应该提供哪些方法，甚至不清楚树是什么。

这就解释了为什么没有 STL 支持：STL 用于大多数人需要的数据结构，基本上每个人都同意什么是合理的接口和有效的实现。对于树来说，这样的事情根本不存在。

血淋淋的细节

如果想进一步了解问题所在，请继续阅读。否则，上面的段落应该足以回答您的问题。

我说连通用接口都没有。您可能不同意，因为您只考虑了一个应用程序，但是如果您进一步考虑它，您会发现树上有无数可能的操作。您可以拥有一个数据结构来有效地启用它们中的大多数，但因此总体上更复杂并且具有该复杂性的开销，或者您拥有更简单的数据结构，只允许基本操作，但这些操作尽可能快。

如果您想要完整的故事，请查看 我关于该主题的论文。在那里，您将找到可能的接口、不同实现的渐近复杂性、问题的一般描述以及更多可能实现的相关工作。

什么是树？

它已经从您认为是一棵树的东西开始：

• 有根或无根：大多数程序员想要有根，大多数数学家想要无根。 （如果您想知道什么是无根的：A - B - C 是一棵树，其中 A、B 或 C 都可以是根。有根树定义了哪个是根。无根树没有）
• 单根/连接或多根/断开连接（树或林）
• 兄弟顺序是否相关？如果不是，那么树结构是否可以在内部重新排序更新时的子级？如果是这样，则不再定义兄弟之间的迭代顺序。但是对于大多数树来说，兄弟顺序 实际上 没有意义，并且允许数据结构在更新时对子节点重新排序对于某些更新非常有利。
• 真的只是一棵树，或者也允许 DAG 边缘（听起来很奇怪，但许多最初想要一棵树的人最终想要一个 DAG）
• 贴标签还是不贴标签？你需要存储每个节点的任何数据，还是只是你感兴趣的树结构（后者可以 非常 简洁地存储）

查询操作

在我们弄清楚我们定义的树之后，我们应该定义查询操作：基本操作可能是“导航到子节点，导航到父节点”，但还有更多可能的操作，例如：

• 导航到下一个/上一个兄弟：即使大多数人都认为这是一个非常基本的操作，如果你只有一个父指针或一个子数组，这实际上几乎是不可能的。因此，这已经向您表明，根据您需要的操作，您可能需要完全不同的实现。
• 按前/后顺序导航
• 子树大小：当前节点的（传递）后代的数量（可能在 O(1) 或 O(log n) 中，即不要只枚举它们全部计数）
• 当前节点中树的高度。即从这个节点到任何离开节点的最长路径。同样，在小于 O(n) 的时间内。
• 给定两个节点，找到该节点的最小共同祖先（使用 O(1) 内存消耗）
• 在前序/后序遍历中，节点 A 和节点 B 之间有多少个节点？ （少于 O(n) 运行时间）

我强调这里有趣的是这些方法是否可以比 O(n) 执行得更好，因为仅枚举整个树始终是一种选择。根据您的应用程序，某些操作比 O(n) 更快可能是绝对关键的，或者您可能根本不关心。同样，根据您的需要，您将需要非常不同的数据结构。

更新操作

到目前为止，我只讨论了查询操作。但现在要更新了。同样，可以通过多种方式更新树。根据您的需要，您需要或多或少复杂的数据结构：

• 叶更新（简单）：删除或添加叶节点
• 内部节点更新（更难）：移动或删除移动内部节点，使其子节点成为其父节点的子节点
• 子树更新（更难）：移动或删除以节点为根的子树

只是给你一些直觉：如果你存储一个子数组并且你的兄弟顺序很重要，即使删除一个叶子也可能是 O(n) 因为它后面的所有兄弟都必须在其父数组的子数组中移动。相反，如果您只有一个父指针，则叶删除是微不足道的 O(1)。如果您不关心兄弟顺序，则子数组也是 O(1)，因为您可以简单地将间隙替换为数组中的最后一个兄弟。这只是一个示例，不同的数据结构将为您提供完全不同的更新功能。

在父指针的情况下，移动整个子树再次简单地 O(1)，但如果您有一个存储所有节点的数据结构，例如按预购顺序，则可能是 O(n)。

然后，有一些正交的考虑，比如如果你执行更新，哪些迭代器保持有效。一些数据结构需要使整个树中的所有迭代器都无效，即使你插入了一个新的叶子。其他人仅使树中被更改的部分中的迭代器无效。其他人保持所有迭代器（已删除节点的迭代器除外）有效。

空间考虑

树结构可以非常简洁。如果您需要节省空间（例如，DFUDS 或 LOUDS，请参阅 此说明 以了解要点），每个节点大约两个位就足够了。但是当然，天真地，即使是父指针也已经是 64 位了。一旦你选择了一个很好导航的结构，你可能宁愿每个节点需要 20 个字节。

有了很多复杂性，人们还可以构建 一个每个条目只需要一些位的数据结构，可以有效地更新，并且仍然可以渐近快速地实现所有查询操作，但这是一个非常复杂的结构的野兽。我曾经开设了一门实践课程，让研究生实施这篇论文。他们中的一些人能够在 6 周内实施它（！），其他人则失败了。虽然该结构具有很好的渐近性，但它的复杂性使其对于非常简单的操作具有相当大的开销。

同样，没有一种万能的。

结论

我花了 5 年时间寻找表示树 的最佳 数据结构，尽管我想出了一些并且有相当多的相关工作，但我的结论是没有。根据用例，高度复杂的数据结构将优于简单的父指针。甚至为树定义接口也很困难。我尝试在我的论文中定义一个，但我必须承认在各种用例中我定义的接口太窄或太大。所以我怀疑这是否会出现在 STL 中，因为调音旋钮太多了。

原文由 gexicide 发布，翻译遵循 CC BY-SA 4.0 许可协议