二叉搜索树分析

Question

在二叉搜索树中，大多数操作的平均计算复杂度为O（NlogN）。以下是来自Algo书中的文本片段：

内部路径长度的平均值是D（n）= O（n log n）。因此， 的任何节点的预期深度是O（log n）。例如，随机生成的500个节点的树具有预期深度为9.98的节点。

立即说这个结果意味着所讨论的所有操作的平均运行时间，即插入， 在二叉搜索树上查找min，find max，delete是O（log n），但是这个 并不完全正确。原因在于，由于 删除，所有二叉搜索树可能均等于 并不清楚。特别是，上述删除算法有利于 使得左侧子树比右侧更深，因为我们总是用 替换具有来自右侧子树的节点的删除节点。这种策略的确切效果仍然不得而知，但它似乎只是一个理论上的新颖性 。已经示出，如果我们交替插入 和缺失O（N 2）（即，n正方形的THETA）倍，则树 将具有THETA平方根N.

的预期深度的四分之一之后百万个随机插入/删除对，该树有点右 - 重看起来明显不平衡（平均深度= 12.51）。

我上面的文字片断的问题是：

1. 什么是笔者的意思是“因为缺失的，目前尚不清楚，所有的二叉搜索树都同样可能”？
2. 作者如何达到500节点树的预期深度9.98，因为日志500不是9.98？
3. 在最后一段中，他是如何获得12.51的平均深度的？

谢谢！

Answer 1

1）它考虑由（有点均匀的）随机插入和删除序列生成的二叉树。当只进行插入时，树的所有可能的形状（高达symetry !!）的大小都是相当可能的 - 你可以尝试构建一个树，其中所有可能的排列为（1,2,3）或（1,2 ，3,4）。

在这里描述的算法中，当删除具有两个子树的节点时，它被右子树取代，并且我猜左子树在最下面。这不仅使得一些（不平衡的）形状比没有删除的可能性更大，而且使得它们可能比左侧树枝上的树更深于右侧树上的树（看看当你移除或接近几个节点时会发生什么采用这种策略的平衡树的根）

2）改为考虑大小511。如果树完全平衡，它将具有深度9（log（n + 1））这是具有许多元素的最小深度。对于随机形状，这是最小值，而不是平均值，平均值必须更大：有深度为511的形状（注意，虽然深度必须大于log2（N），但仍可能为O（logN）） 。我不知道作者是如何得到这个数字的。也许聪明的数学，也许只是运行一个大样本。

4）我相信在这种情况下运行一个样本：树有权重看起来。但很明显，删除将平均倾向于使树木不那么平衡