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

Question

有人能告诉我使用 AVL 是否优于使用 2-3 树，反之亦然，为什么会这样？

谢谢

Answer 1

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

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

如果您的键是字符串，ternary search tries提供 AVL 树的合理替代方案。