如何确定要选择哪种树数据结构？

Question

好吧，这件事一直困扰着我。我知道的树数据结构是：

• 不平衡二叉树
• AVL树
• 红黑树
• 2-3棵树
• B-树
• B*-树木
• 试一试
• 堆

如何确定哪种树是最适合这项工作的工具？显然，堆通常用于形成优先级队列。但剩下的似乎是不同的方式来做同样的事情。有没有办法选择最适合这份工作的？

Answer 1

让我们一个接一个地把它们摘下来，好吗？

• 不平衡二叉树

对于搜索任务，永远不要。基本上，它们的性能特性将是完全不可预测的，平衡树的开销不会太大，从而使不平衡的树成为可行的替代方案。

除此之外，不平衡的二叉树当然还有其他用途，但不是作为搜索树。

• AVL树

它们很容易开发，但它们的性能通常被其他平衡策略所超越，因为平衡它们相对来说是时间密集型的。维基百科声称表示，它们在查找密集型场景中表现得更好，因为在最坏的情况下，它们的高度略低一些。

• 红黑树

这些在大多数C++的std::map实现中使用，可能也在其他一些标准库中使用。但是，由于现代CPU的缓存行为，在每个场景中它们实际上都比B(+)树差。在历史上，当缓存不那么重要(或者说没有那么好)时，当在主内存中使用时，缓存就会超过B树。

• 2-3棵树
• B-树
• B*-树木

这些都需要对所有的树进行最仔细的考虑，因为使用的不同常量基本上是“神奇的”constans，它们以奇怪的、有时是不可预测的方式与底层的硬件体系结构相关联。例如，每个级别的最佳子节点数可能取决于内存页或缓存行的大小。

我不知道有什么好的，一般的规则来区分他们。

• 试一试

完全不同。尝试也是搜索树，但用于检索语料库中的子字符串。trie是一个未压缩的前缀树(即从根到叶节点的路径对应于给定字符串的所有前缀的树)。

尝试应该与后缀树、后缀数组和q-gram索引进行比较和抵消--而不是与其他搜索树进行比较，因为它们搜索的数据是不同的:后一种索引结构允许因子搜索，而不是语料库中的离散词。

• 堆

正如你已经说过的，它们根本不是搜索树。

Answer 2

与任何其他数据结构一样，您必须了解每种类型的树的特征(搜索、插入和删除操作的复杂性)，以及您选择工具的作业的要求。对于最经常执行的操作类型，具有最佳性能的树通常是作业的最佳工具。

你通常可以在维基百科上找到任何数据结构的一般特征。算法简介还至少有一节(在某些情况下是整个章节)介绍了您所列出的大多数数据结构，因此它是另一个很好的参考。

Answer 3

类似问题：什么时候选择RB树，B树还是AVL树？

我想说的是，可以草率地编写最简单的代码(如果可能的话利用库提供的数据结构)。然后度量它的性能问题，如果有的话。

如果你的表现需要是极端的，阅读康拉德鲁道夫的可怕的答案。:)