通过AVL树的二进制搜索树 [英] Binary search tree over AVL tree

问题描述

据了解， AVL 树和二进制搜索树在平均情况下相同，AVL在最坏情况下击败BST。这给我一个提示，AVL总是优于BSTs，以一切可能的方式与他们互动，或许在平衡实现方面增加一点复杂性。

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屋！