如果 C 表示“独生子”节点的数量(当一个节点的父节点不为 null && 它没有兄弟节点时,该节点被称为独生子),为什么我们对每个具有 N 个节点的 AVL 树都有它: C<=(N/2) ?
最佳答案
考虑一棵高度为 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 树。
关于java - 为什么有N个节点的AVL树会保持C<=N/2?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44355058/