data-structures - 如何确定选择哪种树数据结构？

Question

好的，所以这是一直困扰我的事情。我知道的树数据结构是:

不平衡二叉树

AVL 树

红黑树

2-3棵树

B树

B*-树

尝试

堆

我如何确定哪种树是这项工作的最佳工具？显然，堆被规范地用​​于形成优先级队列。但其余的似乎只是做同一件事的不同方式。有什么办法可以选择最适合工作的人吗？

Answer 1

让我们一一摘下，好吗？

• Unbalanced binary trees

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

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

• AVL trees

它们易于开发，但它们的性能通常被其他平衡策略超越，因为平衡它们相对耗时。 Wikipedia claims它们在查找密集型场景中表现更好，因为在最坏的情况下它们的高度略低。

• Red-black trees

这些在大多数 C++ 中都使用了 std::map实现，也可能在其他一些标准库中。但是，还有 good evidence由于现代 CPU 的缓存行为，它们实际上在每种情况下都比 B(+) 树更糟糕。从历史上看，当缓存不那么重要(或那么好)时，它们在主内存中使用时会超过 B 树。

• 2-3 trees
• B-trees
• B*-trees

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

我不知道区分它们的一般规则。

• Tries

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

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

• Heaps

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