如何证明将关键字1,2,...,2^k - 1依次插入空的AVL树, 最终所得到的树是完全平衡的?

Question

如题, 想了很久没想到, 答案用的是数学归纳法, 不是很理解.

Answer 1

既然是完全平衡树，那第一层有1个节点，第二层有2个，第三层有4个，第i层有2^(i-1)个，即每层每个节点有两个孩子或没有孩子。则k层可以看做k个1为首项，2为公比的等比数列求和，可用公式得共有(1-2^k)/(1-2)=2^k-1个节点。

Answer 2

兄弟，我明白了，设树高H正确，证明树高H+1正确，但是它的右子树只有H-1的高度和符合归纳假设：
所以在一系列插入后右子树的高度会变成H并且右子树完全平衡，然后再插入一个数：根节点不平衡：发生旋转：导致左子树高度为H并且完全平衡：右子树和一开始一样：再插入直到右子树完全平衡。