据我所知，AVL树和Binary Search Trees之间的时间复杂度在平均情况下是相同的，在最坏的情况下AVL击败BST . 这给了我一个提示，即AVL总是优于BST以各种可能的方式与它们进行交互，在 balancer 实现方面可能会增加一些复杂性 .
是否有任何理由首先应该使用BST而不是AVL？
据我所知，AVL树和Binary Search Trees之间的时间复杂度在平均情况下是相同的，在最坏的情况下AVL击败BST . 这给了我一个提示，即AVL总是优于BST以各种可能的方式与它们进行交互，在 balancer 实现方面可能会增加一些复杂性 .
是否有任何理由首先应该使用BST而不是AVL？
4 回答
首先，获得最佳性能并不是编程的最终目标 . 因此，即使选项B总是更快并且比A消耗更少的内存，它也不是更好的选择，如果它更好的选择's more complicated. More complicated code takes longer to write, is harder to understand and is more likely to contain bugs. So, if the simpler but less efficient option A is good enough for you, then it means it' .
现在，如果你想在没有 balancer 的情况下将AVL树与简单的二进制搜索树（BST）进行比较，那么AVL将消耗更多的内存（每个节点必须记住它的 balancer 因子）并且每个操作都可以更慢（因为你需要保持 balancer 因素，有时进行轮换） .
如你所说，没有 balancer 的BST有一个非常糟糕（线性）的最坏情况 . 但是如果你知道这个最糟糕的情况如果在极少数情况下操作缓慢的情况下会好转，那么没有 balancer 的BST可能比AVL更好 .
由于检查和更新 balancer 因子和旋转节点会增加额外的开销，因此与非 balancer BST相比，AVL树中的插入和删除可能相当慢 .
由于紧密的 balancer ，搜索永远不会采取类似线性的时间，因此您可能希望在搜索比更新树更频繁的操作的情况下使用AVL树 .
我的假设是：当你提到BST时，你指的是没有 balancer 的BST .
可以说，如果你需要一个可导航的数据结构，并且你知道你的数据不是最坏情况（排序）并且有点小，那么BST（没有 balancer ）就足够了 .
但这很可能是罕见的情况 .
AVL树也是一个BST，但它可以重新 balancer 自己 . 这种行为使得在最坏的情况下更快 . 它保持自我重新 balancer ，因此在最坏的情况下，当普通BST将采用O（n）时，它将消耗O（log n）时间 . 那么，你的问题的答案：实现AVL树总是比普通的BST更好 .