algorithm - 权重平衡树是一棵二叉树，其中每个节点

Question

权重平衡树是一棵二叉树，对于每个节点，左子树中的节点数至少是右子树中节点数的一半，最多是两倍。这样一棵树在 n 个节点上的最大可能高度（从根到最远叶子的路径上的节点数）最好用以下哪项描述？

A.log2(n)

B. log4/3(n)

C.log3(n)

D.log3/2(n)

我的尝试：

左子树中的节点数至少是右子树中节点数的一半，最多是两倍。

树中有 n 个节点，现在一个节点是根节点，剩下 (n-1) 个节点。为了得到树的最大高度，我们将这些（n-1）个节点分成三部分，每部分大小为 n-13 现在在 LST 中保留两部分，在 RST 中保留一部分。LST = 2∗(n-1)/3，且 RST=(n-1)/3

因此，T(n)= T(2/3(n-1) + (n-1)/3) 并且对于最大高度，我们将只考虑 H(n)=H(2/3(n-1)) +1 和 H(1)=0 我尝试使用替换来解决 H(n) Recurrence 但我被困在一个点： 2^k/3^k(nk)=1 这里如何解决 k ？请帮忙

Answer 1

• 你做的几乎是正确的，但递归语句中有一个错误。

• 它应该是这样的：根+左子树+右子树。

• 如果我们将 1 个节点作为根节点，那么它将是 1，其余节点将是 (n-1)。并且从剩余的节点中，我们必须以这样一种方式进行分布，以便我们在以下条件下获得最大高度。

• 让 LST 中的节点为 : nl 并让 RST 中的节点为 : nr

• 方程/条件：nr/2 <= nl <= 2*nr

• 由此我们可以得到 nr 的值，即 n-1/3。计算见图。

• 现在我们到了你犯了错误的地步。

  T(n) = T(n-1/3) + T(2(n-1)/3) + 1其中T(1) = 1且 T(0) = (0)

然后我们最终会得到 log 3/2 n。

图与计算：