math - 简单不平衡搜索树的平均渐近深度是多少？

Question

对于平衡搜索树，所有情况都是 O(log(N))。对于不平衡的搜索树，最坏的情况是 O(N)，例如插入 1,2,3,4,.. 最佳情况复杂度是平衡的情况下，例如插入 6,4,8,3,5 7 . 我们如何定义不平衡搜索树的平均案例复杂度？

Answer 1

二叉树的平均高度是 Theta(sqrt(n))。这已在以下论文中显示（或引用，不太确定）：http ://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf 。

但也许您对随机节点的平均深度更感兴趣，这是 Theta(log n)，如下所示：http ://www.toves.org/books/data/ch05-trees/index.html （第 5.2.4 节）。