二进制搜索vs二进制搜索树

Question

与使用二进制搜索的有序数组相比，二进制搜索树有什么好处？只是通过数学分析，我看不出有什么不同，所以我假设在低级实现开销上一定有不同。对平均案例运行时间的分析如下所示。

使用二进制搜索的排序数组

搜索: O(log(n))

插入: O(log(n)) (我们运行二进制搜索来查找插入元素的位置)

delete: O(log(n)) (我们运行二进制搜索来找到要删除的元素)

二分查找树

搜索: O(log(n))

插入: O(log(n))

删除: O(log(n))

对于上面列出的操作，二进制搜索树的最坏情况是O(n) (如果树不平衡)，所以这看起来实际上比使用二进制搜索的排序数组更糟糕。

此外，我不假设我们必须事先对数组进行排序(这将耗费O(nlog(N)，我们将一个接一个地将元素插入到数组中，就像我们对二叉树所做的那样。我能看到的BST唯一的好处是它支持其他类型的遍历，比如inorder，preorder，postorder。

Answer 1

您的分析是错误的，对于已排序的数组，插入和删除都是O(n)，因为您必须物理地移动和删除数据，以便为插入腾出空间或压缩数据以掩盖已删除的项。

哦，对于完全不平衡的二叉树，最坏的情况是O(n)，而不是O(logn)。

Answer 2

查询任何一个都没有太大的好处。

但是，当您一次添加一个元素时，构建排序树要比构建排序数组快得多。所以当你完成的时候，没有必要把它转换成一个数组。

Answer 3

另请注意，有一些标准算法可用于维护平衡的二进制搜索树。它们摆脱了二叉树的缺点，并保持了所有其他优点。它们很复杂，所以你应该先学习二叉树。

除此之外，大O可能是相同的，但常量并不总是相同的。使用二叉树，如果您正确地存储数据，您可以在多个级别上很好地使用缓存。结果是，如果你要做大量的查询，你的大部分工作都会留在CPU缓存中，这会大大加快速度。如果您在构建树的方式上非常小心，这一点尤其正确。有关巧妙布局树如何极大地提高性能的示例，请参阅http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx。您对其执行二进制搜索的数组不允许使用任何此类技巧。