AVL树和二叉搜索树的比较

Question

据我所知，AVL树和二叉搜索树在平均情况下的时间复杂度相同，在最坏情况下，AVL树胜过BST。这提示我，与BST相比，AVL在与之交互的每种可能方式中始终优于BST，也许在平衡实现方面稍微增加了一些复杂性。

那么，有没有任何理由应该首选BST而不是AVL呢？

- Theocharis K.

---

AVL树已经过时了，现在它们已被红黑树所取代。 - starblue

@starblue 并不完全正确。红黑树的插入性能更快，但查找性能较慢。在处理大量节点时，AVL即使在插入方面也更快。来源：https://dev59.com/UGQo5IYBdhLWcg3wMs0L#28846533 - alx - recommends codidact

Answer 1

首先，获得最佳性能并不是编程的最终目标。因此，即使选项B始终比A更快且消耗的内存更少，如果它更复杂，也不意味着它总是更好的选择。更复杂的代码需要更长的编写时间，更难理解，并且更容易包含错误。因此，如果简单但效率较低的选项A对您来说已经足够好，那么这意味着它是更好的选择。

现在，如果您想将AVL树与简单的未平衡二叉搜索树（BST）进行比较，则AVL将消耗更多的内存（每个节点都必须记住其平衡因子），并且每个操作可能会更慢（因为您需要维护平衡因子并有时执行旋转）。

正如您所说，未平衡的BST具有非常糟糕（线性）的最坏情况。但是，如果您知道这种最坏情况不会发生在您身上，或者如果您可以接受在罕见情况下操作较慢，未平衡的BST可能比AVL更好。

- svick

---

正是我等待的原因。谢谢并接受。 - Theocharis K.

Answer 2

由于需要检查和更新平衡因子以及旋转节点，与非平衡二叉搜索树相比，AVL树的插入和删除可能会比较慢。

由于紧密的平衡，搜索永远不会花费线性时间，因此您可能希望在搜索频率高于树更新操作的情况下使用AVL树。

- lalilulelo

Answer 3

我的假设是：当你提到BST时，你指的是没有平衡的BST。

可以说，如果你需要一个可导航的数据结构，并且你知道你的数据不会是最坏情况（排序）并且相对较小，那么BST（无平衡）就足够了。

但更有可能的是这种情况很少见。

- Justin

Answer 4

AVL树也是一种二叉搜索树，但它可以自我平衡。这种行为使得它在最坏情况下更快。它会不断地重新平衡自己，因此在最坏情况下，它将消耗O(log n)的时间，而普通的BST将需要O(n)的时间。所以，回答你的问题：实现AVL树总是比仅使用普通BST更好。

- gtboy