二分搜索与二叉搜索树

Question

二进制搜索树对具有二分搜索的排序数组有什么好处？只是通过数学分析我没有看到差异,所以我假设低级实现开销必须存在差异.平均病例运行时间的分析如下所示.

使用二进制搜索
搜索的排序数组:O(log(n))
插入:O(log(n))(我们运行二进制搜索以查找插入元素的位置)
删除: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

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

但是,当您一次添加一个元素时,构造排序树比构建排序数组要快得多.所以当你完成时将它转换为数组是没有意义的.