给出n节点二叉搜索树高度的渐近上界,其中节点的平均深度为Θ(lg n)

Question

最近,我正在尝试解决CLRS中的所有练习.但有一些我无法弄清楚.这是其中之一,来自CLRS练习12.4-2:

描述n个节点上的二叉搜索树,使得树中节点的平均深度为Θ(lg n),但树的高度为ω(lg n).给出n节点二分搜索树高度的渐近上界,其中节点的平均深度为Θ(lg n).

任何人都可以分享一些想法或参考来解决这个问题吗？谢谢.

Answer 1

所以我们假设我们以这种方式构建树:给定n个节点,取f(n)个节点并将它们放在一边.然后通过构建一个完美的二叉树来构建树,其中根有一个左子树,它是n - f(n) - 1个节点的完美二叉树,右子树是长度为f(n)的链.我们稍后会选择f(n).

那么树上的平均深度是多少？因为我们只想要一个渐近界,所以让我们选择n使得n - f(n) - 1比2的完美幂小1,比如2 ^ k - 1.在这种情况下,这个中的高度之和树的一部分是1*2 + 2*3 + 4*4 + 8*5 + ... + 2 ^(k-1)*k,这是(IIRC)约k 2 ^ k,这是关于(n - f(n))log(n - f(n))由我们选择k.在树的另一部分中,总深度约为f(n)^ 2.这意味着平均路径长度约为((n-f(n))log(n-f(n))+ f(n)^ 2)/ n.此外,树的高度是f(n).因此,我们希望在保持平均深度O(log n)的同时最大化f(n).

要做到这一点,我们需要找到f(n)这样的

1. n - f(n)=Θ(n),或分子中的对数项消失,高度不是对数,
2. f(n)^ 2/n = O(log n),或者分子中的第二项变得太大.

如果选择f(n)=Θ(sqrt(n log n)),我认为最大值满足1和2.所以我打赌(虽然我可能完全错了)这是你能得到的最好的.您得到一个高度为Θ(sqrt(n log n))的树,其平均深度为Θ(Log n).

希望这可以帮助!如果我的数学计算结束了,请告诉我.现在已经很晚了,我还没有完成通常的复核检查.:-)