二进制搜索VS二叉搜索树 [英] binary search vs binary search tree

问题描述

什么是二叉搜索树在一个有序数组与二进制搜索的好处？只需用数学分析我看不出有差别，所以我想必须有在低层次的实现开销差别。如下图所示的情况下，平均运行时间分析。

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level implementation overhead. Analysis of average case run time is shown below.

排序数组与折半查找
搜索：O（日志（N））
插入：O（日志（N））（我们运行的二进制搜索，找到要插入的元素）
删除：O（日志（N））（我们运行的二进制搜索，找到要删除的元素）

Sorted array with binary search
search: O(log(n))
insertion: O(log(n)) (we run binary search to find where to insert the element)
deletion: O(log(n)) (we run binary search to find the element to delete)

二叉搜索树
搜索：O（日志（N））
插入：O（日志（N））
删除：O（日志（N））

Binary search tree
search: O(log(n))
insertion: O(log(n))
deletion: O(log(n))

二叉搜索树都为O（n）的最坏情况上面列出的操作（如果树不均衡），所以这看起来像它实际上是比排序数组与折半查找更糟。

Binary search trees have a worst case of O(n) for operations listed above (if tree is not balanced), so this seems like it would actually be worse than sorted array with binary search.

另外，我不是假设我们要阵列预先排序（这将花费O（n日志（N）），我们将插入元素逐个放入数组，就像我们会做的二叉树。 BST的唯一好处，我可以看到的是，它支持其他类型，如序，preorder，后序。

Also, I am not assuming that we have to sort the array beforehand (which would cost O(nlog(n)), we would insert elements one by one into the array, just as we would do for the binary tree. The only benefit of BST I can see is that it supports other types of traversals like inorder, preorder, postorder.

推荐答案

您的分析是错误的，无论是插入和删除是O（n）的排序的数组，因为你必须在物理上的移动的数据以腾出空间插入或COM preSS它来掩盖删除的项目。

Your analysis is wrong, both insertion and deletion is O(n) for a sorted array, because you have to physically move the data to make space for the insertion or compress it to cover up the deleted item.

呵呵，最坏情况下完全不平衡的二叉搜索树为O（n），而不是O（LOGN）。你真的需要刷上了大O记法。

Oh and the worst case for completely unbalanced binary search trees is O(n), not O(logn). You really need to brush up on the big-O notation.

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