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

Question

如果C表示的“独苗”的节点数量（一个节点被称为唯一的孩子时，其父是不是null & &它没有兄弟姐妹），为什么我们的，对于每一个AVL树与N个节点：C < =（N/2）？

Answer 1

考虑高度1的AVL树（即仅由根的）：条件清楚地保持（N = 1，C = 0）。

现在考虑高度2的AVL树有可以是带2个孩子（N = 3，C = O）或与一个子根（N = 2，C = 1）的根部。因此，条件也适用于高度为2的树。

现在假设条件对于高度为h（h> = 2）和h-1的树适用，我们表明它也适用于高度为h的树+1。我们可以用一个高度为h的孩子和另一个高度为h或h-1的孩子取一个新根来构建高度为h + 1的树。这些是唯一允许保持AVL属性完整的配置。两个子树的新根和新根都不是“唯一的孩子”节点。因此，我们有N = 1 + N1 + N2和C = C1 + C2。由于C1 < = N1/2和C2 < = N2/2，我们得到c也< = N/2。

现在，诱导条件适用于各种身高的AVL树。