如何证明二叉搜索树的平均高度为O（logn）？

Question

我想到了一个证明，但无法在纸上画草图。我对二叉搜索树的高度有一个递归关系，那就是

T（n）= T（k）+ T（n-k-1）+1

如果k是根和n-k-1在根的右子树上（并且n =总节点），则k是左子树中的元素数]

（如果上面的事情不对，请纠正我）

现在我在想什么，因为我们必须计算平均情况。因此，将有一半的情况可能...（现在这是我开始弄乱这里正确的地方的地方。）

我的主张：在所有可能的情况下，我将有大约一半的情况。范例

根

（0，N-1）或（1，N-2）或。。（N-1,0）

其中N是总节点数。现在，我正在考虑将上述案例的一半用于平均案例计算...（我不知道我是否在正确执行此操作。对此发表的评论将不胜感激）

所以我得到了：

T（n）= T（n / 2）+ T（n / 2）+1

T（n）= 2T（n / 2）+1

现在，当我应用主方法来获得所获得的递归关系的近似答案时。我得到O（n）。

现在我应该如何进行...？（我的期望是我应该登录而不是n）但这并没有解决..因此，plz建议我应如何进一步进行。（我的方法从一开始就完全正确吗？从头开始，还要告诉我有关的内容吗？）

Answer 1

摘自Robert Sedgewick和Kevin Wayne的“算法”>

定义。二进制搜索树（BST）是一个二进制树，其中每个节点都有一个可比较的密钥（和关联值）并满足该密钥的限制在任何节点中，其大小都大于该节点的左子树中所有节点的键，并且小于该节点的右子树中所有节点的键。

Proposition C。

使用N个随机关键字构建的BST中的搜索匹配项需要2 ln N（约1.39 lg N）进行比较。

证明：

用于在给定节点处结束的搜索命中的比较数为1加深度。加上所有节点的深度，我们得到一个称为树的内部路径长度。因此，所需的数量为1加上BST的平均内部路径长度，我们可以使用相同的参数进行分析，即我们在第2.3节中用于命题K：令CN为内部总路径长度通过插入N个随机排序的不同键构建的BST的结果，因此平均值搜索命中的成本是1 CN /N。我们有C0 = C1 = 0，并且对于N> 1，我们可以写一个直接反映递归BST结构的递归关系：

CN = N 1（C0 CN1）/ N +（C1 CN2）/ N。 。 。 （CN1 C0）/ N

N 1项考虑到根对路径长度贡献1树中其他N 1个节点中的每一个；其余的表达方式对于子树，它们很可能是N个大小中的任何一个。重新排列后术语，这种重复几乎与我们在第2.3节中解决的重复相同进行快速排序，我们可以得出近似值CN〜2N ln N

我也建议您查看此Mit讲座Binary Search Trees, BST Sort

也请查阅算法书籍中的第3.2章，它深入解释了二进制搜索树