維基百科的一個不平衡AVL樹的例子是如何不平衡的？

Question

上面的圖像來自"Wikipedia's entry on AVL trees"維基百科指示不平衡。 這棵樹如何不平衡已經？ 下面是文章報價：

節點的平衡因子是它的右子樹的高度減去它的左子樹的高度，並與平衡因子1,0節點，或-1被認爲是平衡。具有任何其他平衡因子的節點被認爲是不平衡的，並且需要重新平衡樹。平衡因子可以直接存儲在每個節點或從子樹的高度計算。

左側和右側子樹的高度均爲4.左側樹的右側子樹高度爲3，仍然只有1小於4.有人可以解釋我錯過了什麼嗎？

Answer 1

均衡，樹中的每個節點必須，或者說，

• 沒有孩子，（是一個「葉」節點）
• 有兩個孩子。

• 或者，如果它只有一個孩子，那個孩子必須是一片葉子。

  在您發佈的圖表中，9,54 & 76違反了最後一條規則。

適當的平衡，樹看起來像：

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

UPDATE：（經過近9年，我在draw.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) > 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 

對於其他節點可以進行類似的計算。