＋设为首页 ＋添加到收藏夹
将关键码1，2，3，...，2^k-1依次插入到一棵初始为空的AVL树中，试证明结果树是完全平衡的。
怎么证？
用归纳法证明
K=1和2、3时命题都成立，设K为任一整数也成立，证明K+1成立。
无论已向AVL中插了多少关键字，下一个字必插在树的最右边叶子的右儿子处。
当K=2时，有2^k-1个叶子的满二叉树再加入2^K个字就变为有2^-1个叶子的满二叉树，设
“有2^-1个叶子的满二叉树再加入2^个字就变为有2^k-1个叶子的满二叉树”成立，证明“有2^k-1个叶子的满二叉树再加入2^K个字就变为有2^-1个叶子的满二叉树”。
假设已插了2^k-1个字形成满二叉树，根的左右子树均是有2^-1个叶子的满二叉树，这时对于根的右子树必须连续插2^个字使得根的右子树成有2^k-1个叶子的满二叉树，而且这时整个树左子树比右子树高度差1，当再向根的右子树插一个字时，整个二叉树将不平衡，需向左旋转，转后根的左子树是个有2^k-1个叶子的满二叉树，而右子树是一个有2^-1个叶子的满二叉树加上最右边叶子的右儿子，左右平衡，这时再加2^个叶子给根的右子树，使得根的左右子树均为2^k-1个叶子的满二叉树。整个树就是有2^-1个叶子的满二叉树，完全平衡。
用以上思想可证明。
不对之处请求赐教！
我觉得可以用数学归纳法，再加上AVL的性质可证。归纳基础很容易验证，假设n=k-1，k>1时，结论成立，则n=k时，考虑1，2，3，...，2^k-1这2^k-1个数的中间值2^(k-1),在它之前的数一定位于它的左子树上，因左子树一定为AVL树，它一定为完全平衡的，对该数后面的数同理可证。
