我曾想过一个证明，但无法在纸上勾画出来。我认为二元搜索树高度的递归关系是
T(n(=T(k(+T(n-k-1(+1
其中k是左子树中的元素数，如果根和n-k-1在根的右子树上(并且n=总节点(
(如果上面的错误，请纠正我(
现在我想的是，因为我们必须计算平均情况。。所以可能有一半的情况。。。(现在这是我开始把事情搞砸的地方，请在这里纠正。(
我的主张：在所有可能的情况下，我会有大约一半的病例。。示例
根
(0，N-1(OR(1，N-2(或。。(N-1,0(
其中N是节点总数。现在，我正在考虑以上一半的案例进行平均案例计算。。。(我不知道我做这件事是否正确。对此发表评论将不胜感激(
所以我得到：
T(n(=T(n/2(+T(n/2
T(n(=2T(n/2(+1
现在，当我对所获得的递归关系应用主方法来获得近似答案时。。我得到O(n(。
现在我该如何继续。。。？(我的期望是我应该得到logn，而不是n(但这并没有成功。。因此，请建议我如何继续。(我的方法是否正确……从一开始，也告诉我这一点？(
摘自Robert Sedgewick和Kevin Wayne 的《算法》
定义。二进制搜索树(BST(是一种二进制树，其中每个节点都有一个可比较密钥(和相关值(，并满足该密钥的限制in中的键大于该节点的左子树中所有节点中的键，并且小于该节点的右子树中所有结点中的键。
命题C。在由N个随机密钥构建的BST中搜索命中率需要~2ln N(约1.39 lg N(。
证明：用于在给定节点结束的搜索命中的比较次数为1加上深度。将所有节点的深度相加，我们得到一个称为树的内部路径长度。因此，所需的数量是1加上BST的平均内部路径长度，我们可以用相同的论点来分析我们在第2.3节中使用了命题K：设CN为总内部路径长度通过插入N个随机排序的不同密钥构建的BST，使得搜索命中的代价是1 CN/N。我们有C0＝C1＝0，对于N>1，我们可以写一个直接反映递归BST结构的递归关系：
CN=N1(C0 CN1(/N+(C1 CN2(/N。(CN1 C0(/N
N1项考虑到根对路径长度的贡献为1树中的其他N1个节点中的每一个节点；表达式的其余部分说明对于子树，它们同样可能是N个大小中的任何一个。重新排列后就术语而言，这种递归与我们在第2.3节中解决的问题几乎相同对于快速排序，我们可以导出近似CN~2N ln N
我也建议你检查这个Mit讲座二进制搜索树，BST排序
还可以查看算法书籍的第3.2章，它解释了深度中的二进制搜索树