给出 n 节点二叉搜索树高度的渐近上限，其中节点的平均深度为 Θ(lg n)
最近，我正在尝试解决 CLRS 中的所有练习。但有些我无法弄清楚。以下是来自 CLRS 练习 12.4-2 的其中之一：
描述 n 个节点上的二叉搜索树，使得树中节点的平均深度为 θ(lg n)，但树的高度为 ω(lg n)。给出 n 节点二叉搜索树高度的渐近上限，其中节点的平均深度为 θ(lg n)。
谁能分享一些想法或参考来解决这个问题？谢谢。
Recently, I'm trying to solve all the exercises in CLRS. but there are some of them i can't figure out. Here is one of them, from CLRS exercise 12.4-2:
Describe a binary search tree on n nodes such that the average depth of a node in the tree is Θ(lg n) but the height of the tree is ω(lg n). Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n).
Can anyone share some ideas or references to solve this problem? Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
因此，假设我们以这种方式构建树：给定 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)。所以我们想要最大化 f(n)，同时保持平均深度 O(log n)。
为此，我们需要找到 f(n)，使得
如果你选择 f(n) = θ(sqrt(n log n))，我认为 1 和 2 得到最大程度的满足。所以我敢打赌（尽管我可能完全错了）这已经是你能得到的最好的了。您将得到一棵高度为 θ(sqrt(n log n)) 且平均深度为 θ(Log n) 的树。
希望这有帮助！如果我的数学成绩很差，请告诉我。现在已经很晚了，我还没有进行平常的双重检查。 :-)
So let's suppose that we build the tree this way: given n nodes, take f(n) nodes and set them aside. Then build a tree by building a perfect binary tree where the root has a left subtree that's a perfect binary tree of n - f(n) - 1 nodes and a right subtree that's a chain of length f(n). We'll pick f(n) later.
So what's the average depth in the tree? Since we just want an asymptotic bound, let's pick n such that n - f(n) - 1 is one less than a perfect power of two, say, 2^k - 1. In that case, the sum of the heights in this part of the tree is 1*2 + 2*3 + 4*4 + 8*5 + ... + 2^(k-1) * k, which is (IIRC) about k 2^k, which is just about (n - f(n)) log (n - f(n)) by our choice of k. In the other part of the tree, the total depth is about f(n)^2. This means that the average path length is about ((n - f(n))log (n - f(n)) + f(n)^2) / n. Also, the height of the tree is f(n). So we want to maximize f(n) while keeping the average depth O(log n).
To do this, we need to find f(n) such that
If you pick f(n) = Θ(sqrt(n log n)), I think that 1 and 2 are satisfied maximally. So I'd wager (though I could be totally wrong about this) that this is as good as you can get. You get a tree of height Θ(sqrt(n log n)) that has average depth Θ(Log n).
Hope this helps! If my math is way off, please let me know. It's late now and I haven't done my usual double-checking. :-)
首先最大化树的高度。 （有一棵树，其中每个节点只有一个子节点，因此有一条向下的长链）。
检查平均深度。 （显然平均深度会太高）。
如果平均深度太高，则必须将树的高度减一。
有很多方法可以将树的高度减一。选择使平均高度最小化的方式。 （通过归纳证明，每次都应该选择使平均高度最小化的那个）。继续下去，直到您低于平均身高要求。 （例如，使用归纳法计算高度和平均深度的公式）。
first maximize the height of the tree. (have a tree where each node only has one child node, so you have a long chain going downward).
Check the average depth. (obviously the average depth will be too high).
while the average depth is too high, you must decrease the height of the tree by one.
There are many ways to decrease the height of the tree by one. Choose the way which minimizes the average height. (prove by induction that each time you should select the one that minimizes the average height). Keep going until you fall under the average height requirement. (e.g. calculate using induction a formula for the height and the average depth).
如果您试图最大化树的高度，同时最小化树中所有节点的平均深度，那么明确的最佳形状将是“伞”形状，例如具有 k 的完整二叉树节点和高度 = lg k，其中 0 < k＜ n，以及来自完整部分的叶子之一的 nk 个节点的单个路径或“尾部”。这棵树的高度大致为 lg k + n - k。
现在让我们计算所有节点的总深度。完整部分的节点深度之和为 sum[ j * 2^j ]，其中和取自 j=0 到 j=lg k。通过一些代数，结果的主项是 2k lg k。
接下来，尾部深度的总和由 sum[i + lg k] 给出，其中总和是从 i=0 到 i=nk 获取的。通过一些代数，结果大约为 (nk)lg k + (1/2)(nk)^2。
因此，将上述两部分相加并除以 n，所有节点的平均深度为 (1 + k/n) lg k + (nk)^2 / (2n)。请注意，因为 0 < k＜ n，无论我们选择什么 k，这里的第一项都是 O(lg n)。因此，我们只需要确保第二项是 O(lg n) 。为此，我们要求 (nk)^2 = O(n lg n)，或 k = n - O(sqrt(n lg n))。通过这种选择，树的高度为
lg k + n - k = O( sqrt(n lg n) )
这渐近地大于普通的 O(lg n) ，并且渐近地是您可以制作树的最高高度保持平均深度为 O(lg n)
If you are trying to maximize the height of a tree while minimizing the average depth of all the nodes of the tree, the unambiguous best shape would be an "umbrella" shape, e.g. a full binary tree with k nodes and height = lg k, where 0 < k < n, along with a single path, or "tail", of n-k nodes coming out of one of the leaves of the full part. The height of this tree is roughly lg k + n - k.
Now let's compute the total depth of all the nodes. The sum of the depths of the nodes of the full part is sum[ j * 2^j ], where the sum is taken from j=0 to j=lg k. By some algebra, the dominant term of the result is 2k lg k.
Next, the sum of the depths of the tail part is given by sum[i + lg k], where the sum is taken from i=0 to i=n-k. By some algebra, the result is approximately (n-k)lg k + (1/2)(n-k)^2.
Hence, summing the two parts above together and dividing by n, the average depth of all the nodes is (1 + k/n) lg k + (n-k)^2 / (2n). Note that because 0 < k < n, the first term here is O(lg n) no matter what k we choose. Hence, we need only make sure the second term is O(lg n). To do so, we require that (n-k)^2 = O(n lg n), or k = n - O(sqrt(n lg n)). With this choice, the height of the tree is
lg k + n - k = O( sqrt(n lg n) )
this is asymptotically larger than the ordinary O(lg n), and is asymptotically the tallest you can make the tree while keeping the average depth to be O(lg n)