data-structures - AVL 树和 2-3 树之间的偏好

Question

有人可以告诉我使用 AVL 是否比使用 2-3 树更可取，反之亦然，为什么会这样？

谢谢

Answer 1

我自己在各种平衡二叉树中的偏好是 AVL 树。它们比任何替代方案都更易于编程（请参阅我的实现here和here，并注意即使删除也不是特别复杂），因为需要考虑的情况更少，它们提供了非常快的查找（因为它们更严格比替代方案更平衡），并且没有隐藏的最坏情况或摊销时间限制。

我通常也更喜欢 AVL 树而不是哈希表。我知道哈希表的预期时间复杂度胜过 AVL 树的保证时间复杂度，但在实践中，常数因素使这两种数据结构通常具有竞争力，并且不会担心一些会引起不良行为的意外数据。此外，我经常发现在程序的维护生命周期中的某个时候，在未预见到的情况下，哈希表的初始选择似乎是正确的，我需要按排序顺序的数据，所以我最终重写程序以使用AVL 树而不是哈希表；这样做足够多的时间，你就会知道你不妨从 AVL 树开始。

如果您的键是字符串，则三元搜索尝试为 AVL 树提供了一个合理的替代方案。