我们知道朴素二叉搜索树会退化为队列,这时search()的时间复杂度为\(O(n)\)
一般地,search()的时间复杂度为\(O(h)\),\(h\)为BST高度
那么朴素BST的平均高度是多少呢?
以下有两种统计口径:
- 随机生成
将一组数以随机的顺序插入BST中,求BST的平均高度
平均高度为\(logn\)
- 随机组成
异构BST高度进行平均
结果为\(Catalan(n)\)
平均查找长度为\(O(\sqrt n)\)
两个结论哪个更为可信呢?
答案:后者。前者中不同的关键码序列会生成同一棵BST
我的疑惑:统计口径2更符合实际的前提是,每一种拓扑排列权值相同。但是事实真的是如此吗?
统计口径1不正说明,有些拓扑结构更容易出现(213 231是同一种拓扑结构)吗?
尝试解答:虽然不能给出严格证明,但是直观来看,经过无数此增删改,树每一种拓扑结构的概率应该趋于相同