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

Question

有人可以告诉我,如果使用AVL比使用2-3树更受欢迎,反之亦然,为什么会这样？

谢谢

Answer 1

在各种平衡二叉树中，我个人最喜欢的是 AVL 树。它们比任何替代方案都更容易编程（请参阅此处和此处的我的实现，并注意即使删除也不是特别复杂），因为需要考虑的情况较少，它们提供的查找速度稍快一些（因为它们更严格）比替代方案平衡），并且没有隐藏的最坏情况或摊销时间限制。

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

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