据我所知，AVL树和二叉搜索树之间的时间复杂度在平均情况下是相同的，在最坏的情况下 AVL 会击败 BST。这给了我一个提示，AVL 在与它们交互的所有可能方式上总是优于 BST，在平衡实现方面可能会增加一点复杂性。
有什么理由有人应该首先使用 BST 而不是 AVL？
问问题
29768 次
4 回答
24
首先，获得最佳性能并不是编程的最终目标。因此，即使选项 B 总是比 A 更快并且消耗的内存更少，但这并不意味着它总是更好的选项，如果它更复杂的话。更复杂的代码需要更长的时间来编写，更难理解并且更有可能包含错误。因此，如果更简单但效率较低的选项 A 对您来说足够好，那么这意味着它是更好的选择。
现在，如果你想在没有平衡的情况下将 AVL 树与简单二叉搜索树 (BST) 进行比较，那么 AVL 会消耗更多的内存（每个节点都必须记住它的平衡因子）并且每次操作会更慢（因为你需要保持平衡因素，有时执行旋转）。
正如您所说，没有平衡的 BST 有一个非常糟糕（线性）的最坏情况。但是如果你知道这种最坏的情况不会发生在你身上，或者如果在极少数情况下操作很慢你还可以，那么没有平衡的 BST 可能比 AVL 更好。
于 2013-02-03T14:20:59.480 回答
2
由于检查和更新平衡因子和旋转节点会增加开销，因此与非平衡 BST 相比，AVL 树中的插入和删除可能非常慢。
由于紧密平衡，搜索永远不会花费类似线性的时间，因此您可能希望在搜索比更新树更频繁的操作的情况下使用 AVL 树。
于 2013-07-07T09:18:10.553 回答
0
我的假设是：当您提到 BST 时，您的意思是没有平衡的 BST。
可以说，如果您需要一个可导航的数据结构并且您知道您的数据不会是最坏的情况（已排序）并且有点小，那么 BST（没有平衡）就足够了。
但很可能这是一种罕见的情况。
于 2013-02-03T14:01:13.413 回答
-1
AVL 树也是一个 BST，但它可以重新平衡自己。这种行为使它在最坏的情况下更快。它不断地重新平衡自己，所以在最坏的情况下，当普通 BST 需要 O(n) 时，它会消耗 O(log n) 时间。因此，您的问题的答案是：实现 AVL 树总是比简单的 BST 更好。
于 2013-03-04T18:35:38.830 回答