AVL 树上的二叉搜索树 [英] Binary search tree over AVL tree

问题描述

据我所知 AVL 树和 二叉搜索树 在平均情况下是相同的，在最坏的情况下，AVL 会击败 BST.这给了我一个暗示，即 AVL 在与它们交互的所有可能方式中总是优于 BST，也许在平衡实现方面增加了一点复杂性.

As far as I know the time complexity between AVL trees and Binary Search Trees are the same in average case, with AVLs beating BSTs in worst case scenarios. This gives me a hint that AVLs are always superior than BSTs in every possible way to interact with them, perhaps adding a little complexity when it comes to balance implementations.

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

Is there any reason anyone should use BSTs instead of AVLs in the first place?

推荐答案

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

First, getting the best possible performance is not the ultimate goal of programming. So, even if option B was always faster and consumed less memory than A, it doesn't mean it's always the better option, if it'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's the better choice.

现在，如果你想在不平衡的情况下将 AVL 树与简单的二叉搜索树 (BST) 进行比较，那么 AVL 会消耗更多的内存(每个节点必须记住它的平衡因子)并且每次操作可能会更慢(因为你需要保持平衡系数，有时执行旋转).

Now, if you want to compare AVL tree with simple binary search tree (BST) without balancing, then AVL will consume more memory (each node has to remember its balance factor) and each operation can be slower (because you need to maintain the balance factor and sometimes perform rotations).

正如您所说，没有平衡的 BST 具有非常糟糕的(线性)最坏情况.但是如果你知道这种最坏的情况不会发生在你身上，或者如果在极少数情况下操作很慢你还好，那么没有平衡的 BST 可能比 AVL 更好.

As you said, BST without balancing has a very bad (linear) worst case. But if you know that this worst case won't happen to you, or if you're okay if the operation is slow in rare cases, BST without balancing might be better than AVL.

这篇关于AVL 树上的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！