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

Question

上图来自 “维基百科关于 AVL 树的条目” 维基百科指出这是不平衡的。这棵树怎么还没有平衡呢？这是文章中的引用：

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

左右子树的高度均为4。左树的右子树的高度为 3，仍然只比 4 少 1。有人可以解释我缺少什么吗？

Answer 1

为了保持平衡，树中的每个节点都必须：

• 没有孩子，（是“叶”节点）
• 有两个孩子。

• 或者，如果它只有一个孩子，那么那个孩子一定是一片叶子。

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

适当平衡的话，树看起来像：

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

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

Answer 2

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

Answer 3

直观地说，这是因为它不是那么小。例如，12应该是9和14的父节点。实际上，9没有左子树，所以它不平衡。树是分层数据结构，因此像“平衡”的规则一样。通常适用于每个节点，而不仅仅是根节点。

你是对的，根节点是平衡的，但不是树的所有节点都是。

Answer 4

另一种看待这种情况的方法是任何节点的高度 h 由下式给出：

h = 1 + max（left.height，right.height）

并且只要以下情况，节点就会失衡：

abs（left.height - right.height）＆gt; 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

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