上面的圖像來自"Wikipedia's entry on AVL trees"維基百科指示不平衡。 這棵樹如何不平衡已經？ 下面是文章報價：
節點的平衡因子是它的右子樹的高度減去它的左子樹的高度，並與平衡因子1,0節點，或-1被認爲是平衡。具有任何其他平衡因子的節點被認爲是不平衡的，並且需要重新平衡樹。平衡因子可以直接存儲在每個節點或從子樹的高度計算。
左側和右側子樹的高度均爲4.左側樹的右側子樹高度爲3，仍然只有1小於4.有人可以解釋我錯過了什麼嗎？
均衡，樹中的每個節點必須，或者說，
或者，如果它只有一個孩子，那個孩子必須是一片葉子。
在您發佈的圖表中，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創建的圖形涼爽的在線圖表）
節點76是不平衡的，例如，因爲它的右子樹是高度0的和左邊是高度的3
直觀地，這是因爲它不是儘可能的小。例如，12應該是9和14的父親。因爲它是9，沒有左子樹，所以它不平衡。樹是分層數據結構，因此像「平衡」這樣的規則通常適用於每個節點而不僅僅是根節點。
你是對的，根節點是平衡的，但不是樹的所有節點都是。
另一種方式看這是任何節點的高度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
對於其他節點可以進行類似的計算。
我認爲重點是樹只有在其中的所有子樹都是平衡的。 – JesperE 2008-10-23 18:23:04
所有的葉子節點都需要平衡。 – 2008-10-23 19:18:01