0%

朴素BST的平均高度

我们知道朴素二叉搜索树会退化为队列,这时search()的时间复杂度为\(O(n)\)

一般地,search()的时间复杂度为\(O(h)\)\(h\)为BST高度

那么朴素BST的平均高度是多少呢?

以下有两种统计口径:

  1. 随机生成

将一组数以随机的顺序插入BST中,求BST的平均高度

平均高度为\(logn\)

  1. 随机组成

异构BST高度进行平均

结果为\(Catalan(n)\)

平均查找长度为\(O(\sqrt n)\)


两个结论哪个更为可信呢?

答案:后者。前者中不同的关键码序列会生成同一棵BST


我的疑惑:统计口径2更符合实际的前提是,每一种拓扑排列权值相同。但是事实真的是如此吗?

统计口径1不正说明,有些拓扑结构更容易出现(213 231是同一种拓扑结构)吗?

尝试解答:虽然不能给出严格证明,但是直观来看,经过无数此增删改,树每一种拓扑结构的概率应该趋于相同

看到这里的姐妹一看就要暴富暴美,为什么不让这一天提前一点呢ヾ(≧▽≦*)o