Yang的部落格(轉貼文章請註記來源)

關於AVL-Tree的介紹，網路已經有大量的文章了，但是對於平衡因子(Balance Factor，簡稱BF)的計算方式反而寥寥無幾(還是我關鍵字打錯的關係？)，所以來記錄一下我對於AVL-Tree的平衡因子計算和旋轉的做法。

P.S.應該是沒錯，因為我遇到的題目使用這個方法還沒出錯過，若有錯誤懇請提出，謝謝！

 P.S. AVL-Tree 為中序(Inorder)，也就是LVR，L數值 < V數值 < R數值

平衡因子的算法為該節點往左子樹走到底的步數和往右子樹走到底的步數相減，而相減後的值為-1、0、1則為平衡，若非這三個數則為不平衡。(都從最下層的節點，也就是Leaf開始依序往上算)

簡單來說就是 |左子樹走到底的步數 - 右子樹走到底的步數| ≦ 1

而不平衡的時候則進行旋轉的動作，旋轉的方式分為LL、RR、LR、RL，而且旋轉完候一樣要保持Inorder的順序

(以下圖片皆使用小畫家繪製，難看請見諒...)

先看看平衡因子的算法：

狀況一、

40沒有左子樹和右子樹(皆為NULL，皆走0步)，所以其平衡因子為0

60沒有左子樹和右子樹(皆為NULL，皆走0步)，所以其平衡因子為0

50往左邊走到底只走了1步，往右走到底只走了1步，所以其平衡因子為0

狀況二、

30沒有左子樹和右子樹(皆為NULL，皆走0步)，所以其平衡因子為0

70沒有左子樹和右子樹(皆為NULL，皆走0步)，所以其平衡因子為0

40往左邊走到底只走了1步，而右邊卻沒有右子樹(也就是NULL，走0步)，所以其平衡因子為1

60往右邊走到底只走了1步，而左邊卻沒有左子樹(也就是NULL，走0步)，所以其平衡因子為-1

50往左邊走到底只走了2步，往右走到底只走了2步，所以其平衡因子為0

狀況三、

由於30、35、45、60、70和上面的狀況類似，所以不再解釋了

40往左走到底要走2步(40→30→35)，往右走到底要走1步(40→45)，所以其平衡因子為1

50往左走到底要走3步(50→40→30→35)，往右走到底要走2步(50→60→70)，所以其平衡因子為1

再來看看若不平衡的話，該怎麼處理：

狀況一、

由上面教過的平衡因子算法可以知道此圖已經不平衡了，接著就從最先出現不平衡的那個節點開始往下紀錄路徑

由於是左邊不平衡，所以是LL型(Left-Left)，要進行旋轉的動作！而旋轉後要注意整棵AVL-Tree的Inorder是否和旋轉前相同

旋轉後如下↓

狀況二、

其實同狀況一，只是變成了右邊不平衡，也就是RR型(Right-Right)，同樣進行旋轉且不違反Inorder

狀況三、

先計算平衡因子...

10的平衡因子：0-0=0

20的平衡因子：1-0=1

30的平衡因子：2-0=2

40的平衡因子：3-1=2

45的平衡因子：0-0=0

70的平衡因子：0-0=0

60的平衡因子：0-1=-1

50的平衡因子：4-2=2

計算完畢後發現最早出現不平衡的節點為30，故為LL型！

開始對不平衡的節點和其子樹進行翻轉！

狀況四、

看到下圖，一樣先計算平衡因子

計算完畢後發現不平衡，從最先出現不平衡的點開始記錄路徑，發現是LR型！

而LR型和RL型的翻轉步驟比LL和RR多了一個步驟！！

要先將最先出現不平衡的那個節點下面的子樹先翻轉成LL或RR後(一樣要保持Inorder)，再將這個子樹和最先出現不平衡的節點進行LL或RR翻轉

恩...基本上就是這樣了，如果有錯可以提出來。