问如何形成递归以求权重平衡二叉树的高度？

EN

只有完整的二叉树才能平衡权重。设H(n)是具有精确n内部节点(所以，2*n+1节点)的权重平衡二叉树的最大高度。基本情况

H(0) = 0

很明显。复发

             floor((4*n/3-1)/2)
H(n) = 1 +           max          max(H(l), H(n-1-l))     for all n > 0
           l=ceiling((2*n/3-1)/2)

由于高度的反复出现，并且考虑到n-1内部节点不是根，我们必须将它们分布在左(l)和右(n-1-l)子树之间，但要遵守权重平衡准则。(需要分发2*n内部和外部节点；最不平衡的拆分可能是三分之一/三分之二；带有k节点的完整二叉树具有(k-1)/2内部节点。)

让我们假设H(n)是不减的，并写出一个新的递推

H'(0) = 0
H'(n) = 1 + H'(floor(2*n/3-1/2))     for all n > 0.

新递归的要点是，如果它实际上是不减的，那么H(n) = H'(n)，通过一个强的归纳法证明，其中包括简化另一个递归中的最大值。事实上，我们可以在不求解H'(n)的情况下通过归纳法证明它实际上是不减的，所以这个简化是很好的。

至于求解H'(n)，我会挥手告诉你们，阿克拉-巴兹适用(或者，主定理案例2，如果您想快速和松散地玩floor)，得到渐近界的H'(n) = Theta(log n)。