为什么一个有N个节点的AVL树会保持C<=N/2？
Why does an AVL tree with N nodes maintain C<=N/2?
如果 C 表示 "only child" 个节点的数量（当一个节点的父节点不为 null && 它没有兄弟节点时，该节点被称为独生子节点），为什么我们对每个 AVL 树都有它有 N 个节点：C<=(N/2) ?
考虑一棵高度为 1 的 AVL 树（即仅由根组成）：条件显然成立（N=1，C=0）。
现在考虑高度为 2 的 AVL 树。可以有一个根有 2 children (N=3, C=0) 或一个根有一个 child (N= 2、C=1）。因此，该条件也适用于高度为 2 的树。
现在假设，条件适用于高度为 h (h>=2) 和 h-1 的树，我们证明它也适用于高度为 h+1 的树。我们可以构造一棵高度为 h+1 的树，方法是取一个新根，其中一个 child 高度为 h，另一个 child 高度为 h 或 h-1。这些是保持 AVL 属性 完整的唯一允许配置。新根和两棵子树的根都不是"only child"个节点。因此我们有 N=1+N1+N2 和 C=C1+C2。由于 C1<=N1/2 和 C2<=N2/2 我们也得到 C<=N/2.
现在，通过归纳，该条件适用于所有高度的 AVL 树。
如果 C 表示 "only child" 个节点的数量（当一个节点的父节点不为 null && 它没有兄弟节点时，该节点被称为独生子节点），为什么我们对每个 AVL 树都有它有 N 个节点：C<=(N/2) ?
考虑一棵高度为 1 的 AVL 树（即仅由根组成）：条件显然成立（N=1，C=0）。
现在考虑高度为 2 的 AVL 树。可以有一个根有 2 children (N=3, C=0) 或一个根有一个 child (N= 2、C=1）。因此，该条件也适用于高度为 2 的树。
现在假设，条件适用于高度为 h (h>=2) 和 h-1 的树，我们证明它也适用于高度为 h+1 的树。我们可以构造一棵高度为 h+1 的树，方法是取一个新根，其中一个 child 高度为 h，另一个 child 高度为 h 或 h-1。这些是保持 AVL 属性 完整的唯一允许配置。新根和两棵子树的根都不是"only child"个节点。因此我们有 N=1+N1+N2 和 C=C1+C2。由于 C1<=N1/2 和 C2<=N2/2 我们也得到 C<=N/2.
现在，通过归纳，该条件适用于所有高度的 AVL 树。