algorithm - 二叉搜索树分析

Question

在二叉搜索树中，大多数操作的平均计算复杂度为 O(NlogN)。以下是 Algo 书中的一段文字:

Average of internal path length is D(n) = O(n log n). Thus, the expected depth of any node is O(log n). As an example, the randomly generated 500-node tree has nodes at expected depth 9.98.

It is tempting to say immediately that this result implies that the average running time of all the operations discussed i.e., insert, find min, find max, delete on binary search tree is O(log n), but this is not entirely true. The reason for this is that because of deletions, it is not clear that all binary search trees are equally likely. In particular, the deletion algorithm described above favors making the left subtrees deeper than the right, because we are always replacing a deleted node with a node from the right subtree. The exact effect of this strategy is still unknown, but it seems only to be a theoretical novelty. It has been shown that if we alternate insertions and deletions O(n2) (i.e., theta of n square) times, then the trees will have an expected depth of theta of square root N.

After a quarter-million random insert/delete pairs, the tree that was somewhat right-heavy looks decidedly unbalanced (average depth = 12.51).

我对以上文本片段的问题是:

1. 作者所说的“由于删除，不清楚所有二叉搜索树的可能性均等”是什么意思？
2. 作者如何实现 500 节点树的预期深度 9.98，因为 log 500 不是 9.98？
3. 在上一段中，他是如何获得 12.51 的平均深度的？

谢谢!

Answer 1

1) 它考虑由(有点统一的)随机插入和删除序列生成的二叉树。仅进行插入时，树的所有可能形状(达到对称性!!)对于大小的可能性是相等的 - 您可以尝试构建一棵树，其中包含 (1,2,3) 或 (1,2) 的所有可能排列,3,4).

在这里描述的算法中，当一个节点有两个子树被删除时，它被它的右子树取代，我猜左子树在它下面最左边。这不仅使一些(不平衡的)形状比没有删除时更有可能，而且还使树的左分支比右分支更深(看看当你删除一些节点时会发生什么)使用此策略的平衡树的根)

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

4) 我认为在这种情况下运行样本:树木的看起来很重。然而，很明显，平均而言，删除会使树不那么平衡