最近，我正在尝试解决CLRS中的所有练习。但有一些我无法弄清楚。这是其中之一，来自CLRS练习12.4-2：
描述n个节点上的二叉搜索树，使得树中节点的平均深度为Θ（lg n），但树的高度为ω（lg n）。给出n节点二分搜索树高度的渐近上界，其中节点的平均深度为Θ（lg n）。
任何人都可以分享一些想法或参考来解决这个问题吗？谢谢。
所以我们假设我们以这种方式构建树：给定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）这样的
如果选择f（n）=Θ（sqrt（n log n）），我认为最大值满足1和2。所以我打赌（虽然我可能完全错了），这是你能得到的最好的。您得到一个高度为Θ（sqrt（n log n））的树，其平均深度为Θ（Log n）。
希望这可以帮助！如果我的数学计算结束了，请告诉我。现在已经很晚了，我还没有完成通常的复核检查。 :-)
首先最大化树的高度。 （有一棵树，每个节点只有一个子节点，所以你有一条长链向下）。
检查平均深度。 （显然平均深度太高）。
虽然平均深度太高，但您必须将树的高度减少一个。有许多方法可以将树的高度减少一个。选择最小化平均高度的方法。 （通过归纳证明每次你应该选择最小化平均高度的那个）。继续前进，直到你达到平均身高要求。 （例如，使用感应计算高度和平均深度的公式）。
如果您试图最大化树的高度同时最小化树的所有节点的平均深度，则明确的最佳形状将是“伞形”形状，例如，一个完整的二叉树，其中k个节点和height = lg k，其中0 <k <n，以及从完整部分的一个叶子出来的n-k个节点的单个路径或“尾部”。这棵树的高度大约是lg k + n - k。
现在让我们计算所有节点的总深度。全部的节点的深度之和是sum [j * 2 ^ j]，其中和是从j = 0到j = lg k。通过一些代数，结果的主导项是2k lg k。
接下来，尾部的深度之和由sum [i + lg k]给出，其中总和取自i = 0到i = n-k。通过一些代数，结果是近似（n-k）lg k +（1/2）（n-k）^ 2。
因此，将上述两个部分相加并除以n，所有节点的平均深度为（1 + k / n）lg k +（n-k）^ 2 /（2n）。注意，因为0 <k <n，所以这里的第一项是O（lg n），无论我们选择什么k。因此，我们只需要确保第二项是O（lg n）。为此，我们要求（n-k）^ 2 = O（n lg n），或k = n-O（sqrt（n lg n））。有了这个选择，树的高度就是
lg k + n - k = O（skrt（n ln n））
这是渐近地大于普通的O（lg n），并且渐近地是最高的你可以制作树，同时保持平均深度为O（lg n）