java - 为什么有N个节点的AVL树会保持C<=N/2？

Question

如果 C 表示“独生子”节点的数量(当一个节点的父节点不为 null && 它没有兄弟节点时，该节点被称为独生子)，为什么我们对每个具有 N 个节点的 AVL 树都有它: C<=(N/2) ?

Answer 1

考虑一棵高度为 1 的 AVL 树(即仅由根组成):条件显然成立(N=1，C=0)。

现在考虑高度为 2 的 AVL 树。可以有一个根有 2 个 child (N=3，C=0)，也可以有一个根有一个 child (N=2，C=1)。因此，该条件也适用于高度为 2 的树。

现在假设，条件适用于高度为 h (h>=2) 和 h-1 的树，我们证明它也适用于高度为 h+1 的树。我们可以构造一棵高度为 h+1 的树，方法是取一个新根，其中一个子节点高度为 h，另一个子节点高度为 h 或 h-1。这些是保持 AVL 属性不变的唯一允许的配置。新根和两个子树的根都不是“独生子”节点。因此我们有 N=1+N1+N2 和 C=C1+C2。由于 C1<=N1/2 和 C2<=N2/2，我们也得到 C<=N/2。

现在，通过归纳，该条件适用于所有高度的 AVL 树。