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