data-structures - 维基百科的不平衡 AVL 树的例子是如何真正不平衡的？

Question

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

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

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

Answer 1

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

Answer 2

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

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

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

  在您发布的图表中，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上为图表创建了一个很酷的在线图表）

Answer 3

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

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

Answer 4

另一种看待这一点的方法是，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

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