通过归纳证明对于任何高度为 h 的 AVL 树，直到 h/2 的所有级别都是完整树
Show that for any AVL tree with height h, all levels until h/2 are complete trees by induction
我在测试中遇到了这个问题：“通过归纳法表明，对于给定的高度为 h 的 AVL 树，树的所有级别直到 h/2（向下舍入）都是完全二叉树”。我写下了以下答案，想知道我的论点是否成立。
base: h= 0-> level 0/2 是完全二叉树，因为只有一个根。 h=1-> 相同的参数，因为 1/2 舍入为零
步骤：假定所有具有级别 h 的 avl 树的正确性并显示 h+1。
假设我们有一个高度为 h+1 的 AVL 树。移除根并接收两棵高度为 h 或一棵 h 和一棵 h-1 的 AVL 树。
分为两种情况：h为偶数，h为奇数。
h 是奇数： h/2=(h-1)/2 （向下舍入）所以我们通过归纳得到两棵子树上的相同级别是完整的，加回根，我们得到所有级别 h+ 1/2 完成。
h 是偶数：如果树的高度不同，则 h/2= (h-1)/2 + 1（向下舍入）。因此，由于更高的树在 h/2 之前是完全二叉树，因此他在级别 h-1/2 之前是完全二叉树。加回根，我们得到 h+1/2 是完全二叉树。
我想知道这与正确答案的接近程度。
如果您在缺少括号的地方添加括号，您提供的证明确实是正确的，并进行了其他一些改进。看我更新的粗体字：
base: h= 0-> then level 0/2 is complete binary tree since there's just a root. h=1-> same argument since 1/2 round down is zero.
step: assume correctness for all avl trees with level h and show for h+1. assume we have a AVL tree of height h+1. remove the root and receive two AVL trees of height h or one h and one h-1. divide into two cases: h is even, h is odd. h is odd: h/2=(h-1)/2 (round down) so we get that the same levels on the two sub trees are complete by induction, add back the root and we get that all level (h+1)/2 are complete. h is even: if the trees are of different height then h/2= (h-1)/2 + 1 (round down). so since the taller tree is a complete binary tree until h/2 it stands that he is complete binary tree until level (h-1)/2, which is h/2 - 1 as h is even. add back the root and we get h/2 is complete binary tree.
我在测试中遇到了这个问题：“通过归纳法表明，对于给定的高度为 h 的 AVL 树，树的所有级别直到 h/2（向下舍入）都是完全二叉树”。我写下了以下答案，想知道我的论点是否成立。
base: h= 0-> level 0/2 是完全二叉树，因为只有一个根。 h=1-> 相同的参数，因为 1/2 舍入为零
步骤：假定所有具有级别 h 的 avl 树的正确性并显示 h+1。 假设我们有一个高度为 h+1 的 AVL 树。移除根并接收两棵高度为 h 或一棵 h 和一棵 h-1 的 AVL 树。 分为两种情况：h为偶数，h为奇数。 h 是奇数： h/2=(h-1)/2 （向下舍入）所以我们通过归纳得到两棵子树上的相同级别是完整的，加回根，我们得到所有级别 h+ 1/2 完成。 h 是偶数：如果树的高度不同，则 h/2= (h-1)/2 + 1（向下舍入）。因此，由于更高的树在 h/2 之前是完全二叉树，因此他在级别 h-1/2 之前是完全二叉树。加回根，我们得到 h+1/2 是完全二叉树。
我想知道这与正确答案的接近程度。
如果您在缺少括号的地方添加括号，您提供的证明确实是正确的，并进行了其他一些改进。看我更新的粗体字：
base: h= 0-> then level 0/2 is complete binary tree since there's just a root. h=1-> same argument since 1/2 round down is zero.
step: assume correctness for all avl trees with level h and show for h+1. assume we have a AVL tree of height h+1. remove the root and receive two AVL trees of height h or one h and one h-1. divide into two cases: h is even, h is odd. h is odd: h/2=(h-1)/2 (round down) so we get that the same levels on the two sub trees are complete by induction, add back the root and we get that all level (h+1)/2 are complete. h is even: if the trees are of different height then h/2= (h-1)/2 + 1 (round down). so since the taller tree is a complete binary tree until h/2 it stands that he is complete binary tree until level (h-1)/2, which is h/2 - 1 as h is even. add back the root and we get h/2 is complete binary tree.