最近，我正在尝试解决 CLRS 中的所有练习。但有一些我无法弄清楚。这是其中之一，来自 CLRS 练习 12.4-2：
描述在 n 个节点上的二叉搜索树，使得树中节点的平均深度为 Θ(lg n)，但树的高度为 ω(lg n)。给出一个 n 节点二叉搜索树高度的渐近上限，其中节点的平均深度为 Θ(lg n)。
任何人都可以分享一些想法或参考来解决这个问题吗？谢谢。
问问题
3166 次
3 回答
6
因此，假设我们以这种方式构建树：给定 n 个节点，取 f(n) 个节点并将它们放在一边。然后通过构建一棵完美二叉树来构建一棵树，其中根有一个左子树，它是 n - f(n) - 1 个节点的完美二叉树，右子树是长度为 f(n) 的链。我们稍后会选择 f(n)。
那么树的平均深度是多少？因为我们只想要一个渐近界，所以让我们选择 n 使得 n - f(n) - 1 比 2 的完美幂小一，例如 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) 使得
- n - f(n) = Θ(n)，或者分子中的对数项消失并且高度不是对数，
- f(n)^2 / n = O(log n)，或者分子中的第二项变得太大。
如果你选择 f(n) = Θ(sqrt(n log n))，我认为 1 和 2 是最大的满足。所以我敢打赌（尽管我可能完全错了）这是你能得到的最好的。你得到一棵高度为 Θ(sqrt(n log n)) 的树，它的平均深度为 Θ(Log n)。
希望这可以帮助！如果我的数学很差，请告诉我。现在已经很晚了，我还没有像往常一样仔细检查。:-)
于 2012-02-13T08:48:44.883 回答
0
首先最大化树的高度。（有一棵树，其中每个节点只有一个子节点，所以你有一条长链向下）。
检查平均深度。（显然平均深度会太高）。
当平均深度太高时，您必须将树的高度减一。有很多方法可以将树的高度减一。选择最小化平均高度的方式。（通过归纳证明，每次你应该选择最小化平均高度的那个）。继续前进，直到您低于平均身高要求。（例如，使用归纳公式计算高度和平均深度）。
于 2012-02-13T10:06:16.403 回答
0
如果您试图最大化树的高度同时最小化树的所有节点的平均深度，那么明确的最佳形状将是“伞形”形状，例如具有 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) 的同时渐近地是你可以制作树的最高点
于 2018-01-01T03:49:50.137 回答