维基百科上的不平衡 AVL 树示例如何真正不平衡？

Question

上面的图片来自 < a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow noreferrer">“维基百科关于 AVL 树的条目” 维基百科指出这是不平衡的。 这棵树怎么还没有平衡呢？ 这是文章中的引用：

节点的平衡因子是其右子树的高度减去其左子树的高度，平衡因子为1、0或-1的节点被认为是平衡的。 具有任何其他平衡因子的节点都被视为不平衡，需要重新平衡树。 平衡因子要么直接存储在每个节点上，要么根据子树的高度计算。

左子树和右子树的高度均为 4。左子树的右子树的高度为 3，仍然只比 4 少 1。有人能解释一下我错过了什么吗？

Answer 1

例如，节点 76 是不平衡的，因为它的右子树的高度为 0，左子树的高度为 3。

Answer 2

直观上来说，这是因为它不是越小越好。 例如，12 应该是 9 和 14 的父节点。事实上，9 没有左子树，因此它不平衡。 树是一种分层数据结构，因此“平衡”之类的规则通常适用于每个节点，而不仅仅是根节点。

您是对的，根节点是平衡的，但并非树的所有节点都是平衡的。

Answer 3

另一种看待这个问题的方法是，任何节点的高度 h 均由以下公式给出：

h = 1 + max( left.height, right.height ) ，

并且节点为每当以下情况时不平衡：

abs( left.height - right.height ) > 1

查看上面的树：

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

为了确定节点 9 是否平衡，我们查看其子节点的高度：

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

现在求解以显示节点 9 不平衡：

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

可以对每个其他节点进行类似的计算。

Answer 4

高度平衡的树在很多方面都是最好的！ 对于每个子树，它的子树的高度相差 1 或 0，其中没有子树的高度为零，因此叶子的高度为 1。它是最简单的平衡树，平衡开销最低：最多 2n在高度为 n 的树区域中插入或删除的旋转次数，通常要少得多。 一次循环就是写入 3 个指针，因此非常便宜。 高度平衡树的最坏情况，尽管最大高度高出约 42%，但与 2^n-1 值的完美平衡完整二叉树相比，效率大约低一比较。 完美平衡的完整二叉树的实现成本要高得多，平均而言，对于找到的情况往往需要 n-1 次比较，而对于未找到的情况则总是需要 n-1 次比较。 对于树最坏情况插入顺序，有序数据，当插入2^n-1个项目时，得到的高度平衡树是完美平衡的满二叉树！

（旋转是一种很好的平衡方法，但有一个问题：如果重的孙子位于重的子项的内侧，则一次旋转只会将其移动到另一侧的内侧，没有任何改善。所以，如果是 1 个单位高，即使名义上是平衡的，您首先旋转该子项以减轻它的重量，因此对于 n 层插入或删除最多 2n 次旋转，最坏的情况并且不太可能。）

Answer 5

为了平衡，树中的每个节点必须要么

• 没有子节点，要么（作为“叶”节点）
• 有两个子节点。

• 或者，如果它只有一个子节点，则该子节点必须是一片叶子。

  在您发布的图表中，9, 54 & 76 违反了最后一条规则。

适当平衡后，树看起来像：

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

更新：（近 9 年后，我为该图创建了一个很酷的在线图表 draw.io)