如何形成递归来寻找权重平衡二叉树的高度？

Question

权重平衡树是一棵二叉树，其中对于每个节点，编号。左子树中节点的数量至少是数量的一半，最多是数量的两倍。右子树中的节点数。那么这个权值平衡二叉树的高度是如何形成递归的呢？

Answer 1

只有满二叉树才能weight-balanced。设 H(n) 是 weight-balanced 二叉树的最大高度，正好有 n interior 个节点（因此，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) 子树，符合 weight-balance 标准。（有 2*n 个内部和外部节点要分布；最不平衡的分裂可能是 one-third/two-thirds；具有 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)，我会挥挥手告诉你 Akra--Bazzi 适用（或者，如果你想快速和松散地玩 floor), 产生渐近边界 H'(n) = Theta(log n).

如何形成递归来寻找权重平衡二叉树的高度？

How to form a recurrence for findng the height of a weight balanced binary tree?

algorithm

tree