AVL树上的二叉搜索树

Question

据我所知，AVL树与Binary Search Trees之间的时间复杂度在平均情况下是相同的，AVL在最差情况下击败BST。这给了我一个暗示，AVL在各种可能的方式上总是优于BST，与平衡实现时可能会增加一点复杂性。

是否有任何理由任何人应该首先使用BST而不是AVL？

Answer 1

首先，获得最佳性能是而不是编程的最终目标。因此，即使选项B总是比A更快，消耗的内存也更少，但并不意味着它总是更好的选择，如果它更复杂的话。更复杂的代码需要更长的时间来编写，难以理解，并且更可能包含错误。所以，如果更简单但效率较低的选项A对您来说足够好，那么这意味着它是更好的选择。现在，如果您想将AVL树与简单二叉搜索树（BST）进行比较而不平衡，那么AVL将消耗更多内存（每个节点必须记住它的平衡因子），并且每个操作可能会更慢（因为您需要保持平衡因素并且有时执行旋转）。正如你所说，BST没有平衡有一个非常糟糕的（线性）最坏的情况。但是如果你知道这种最坏的情况不会发生在你身上，或者如果你在没有平衡的情况下操作很慢，那么BST没有平衡可能会比AVL好。

Answer 2

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

如果你需要一个可导航的数据结构，并且你知道你的数据不会是最坏情况（排序）并且有点小，那么BST（没有余额）就足够了。

但更可能是罕见的情况。

Answer 3

AVL树也是BST，但它可以自我平衡。这种行为使得它在最坏的情况下更快。它不断重新平衡自己，所以在最坏的情况下，当平原BST采用O（n）时，它会消耗O（log n）时间。所以，你的问题的答案：实现AVL树比纯BST更好。

Answer 4

由于检查和更新平衡因子和旋转节点会增加开销，因此与非平衡BST相比，AVL树中的插入和删除操作可能非常缓慢。

由于严格的平衡，搜索永远不会像线性一样的时间，所以您可能会希望在搜索比更新树更频繁的情况下使用AVL树。