數(shù)據(jù)結構與算法

1、1 1AVLAVL樹樹 高度平衡的二叉搜索樹高度平衡的二叉搜索樹ABDABCDECEnAVL 樹的定義樹的定義 一棵一棵 AVL 樹或者是空樹，或樹或者是空樹，或者是具有下列性質的二叉搜索樹：它的左子樹者是具有下列性質的二叉搜索樹：它的左子樹和右子樹都是和右子樹都是 AVL 樹，且左子樹和右子樹的樹，且左子樹和右子樹的高度之差的絕對值不超過高度之差的絕對值不超過 1。 2 2結點的平衡因子結點的平衡因子bfbf (balance factorbalance factor)n每個結點附加一個數(shù)字，給出該結點右子樹每個結點附加一個數(shù)字，給出該結點右子樹的高度減去左子樹的高度所得的高度差，這的高度減

2、去左子樹的高度所得的高度差，這個數(shù)字即為結點的平衡因子個數(shù)字即為結點的平衡因子bf。 nAVL樹任一結點平衡因子只能取樹任一結點平衡因子只能取 -1, 0, 1。n如果一個結點的平衡因子的絕對值大于如果一個結點的平衡因子的絕對值大于1，則，則這棵二叉搜索樹就失去了平衡，不再是這棵二叉搜索樹就失去了平衡，不再是AVL樹。樹。n如果一棵有如果一棵有 n 個結點的二叉搜索樹是高度平個結點的二叉搜索樹是高度平3 3衡的，其高度可保持在衡的，其高度可保持在O(log2n)，平均搜，平均搜索長度也可保持在索長度也可保持在O(log2n)。AVLAVL樹的類定義樹的類定義 (略)4 4平衡化旋轉n如果在一棵

3、平衡的二叉搜索樹中插入一個新如果在一棵平衡的二叉搜索樹中插入一個新結點，造成了不平衡。此時必須調整樹的結結點，造成了不平衡。此時必須調整樹的結構，使之平衡化。構，使之平衡化。n平衡化旋轉有兩類：平衡化旋轉有兩類： 單旋轉單旋轉 (左旋和右旋左旋和右旋) 雙旋轉雙旋轉 (左平衡和右平衡左平衡和右平衡)n每插入一個新結點時每插入一個新結點時, AVL 樹中相關結點的樹中相關結點的平衡狀態(tài)會發(fā)生改變。因此平衡狀態(tài)會發(fā)生改變。因此, 在插入一在插入一 個新個新結點后，需要結點后，需要從插入位置沿通向根的路徑回從插入位置沿通向根的路徑回溯溯，檢查各結點的平衡因子檢查各結點的平衡因子。5 5n如果在某一結

4、點發(fā)現(xiàn)高度不平衡，停止回溯。如果在某一結點發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結點起，沿剛才回溯的路徑取從發(fā)生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點。直接下兩層的結點。n如果這三個結點處于一條直線上，則采用單旋如果這三個結點處于一條直線上，則采用單旋轉進行平衡化轉進行平衡化。單旋轉可按其方向分為單旋轉可按其方向分為左單旋左單旋轉轉和和右單旋轉右單旋轉, 其中一個是另一其中一個是另一 個的鏡像，個的鏡像，其方向與不平衡的形狀相關。其方向與不平衡的形狀相關。n如果這三個結點處于一條折線上，則采用雙旋如果這三個結點處于一條折線上，則采用雙旋轉進行平衡化轉進行平衡化。雙旋轉分為雙旋轉分

5、為先左后右先左后右和和先右后先右后左左兩類。兩類。6 6右單旋轉右單旋轉左單旋轉左單旋轉左右雙旋轉左右雙旋轉右左雙旋轉右左雙旋轉左單旋轉左單旋轉 (RotateLeft ) (RotateLeft )n在結點在結點A的右子女的右子女的的右子樹右子樹E中插入新結點，中插入新結點，該子樹高度增該子樹高度增1導致結點導致結點A的平衡因子變成的平衡因子變成2，出現(xiàn)不平衡。為使樹恢復平衡，從出現(xiàn)不平衡。為使樹恢復平衡，從A沿插入路沿插入路徑連續(xù)取徑連續(xù)取3個結點個結點A、C和和E，以結點，以結點C為旋轉為旋轉軸，讓結點軸，讓結點A反時針旋轉。反時針旋轉。7 7插入插入ACEBDhhh-1 h-1BACE

6、Dhhh-1 hBhhCEADh-1 h8 8n在結點在結點A的左子女的左子女的的左子樹左子樹D上插入新結上插入新結點使其高度增點使其高度增1導致結點導致結點A的平衡因子增的平衡因子增到到-2，造成不平衡。為使樹恢復平衡，造成不平衡。為使樹恢復平衡，從從A沿插入路徑沿插入路徑右單旋轉右單旋轉 (RotateRight ) (RotateRight )9 9n插入路徑連續(xù)取插入路徑連續(xù)取3 個結點個結點A、B和和D，以結點，以結點B為旋轉軸，將結點為旋轉軸，將結點A順時針旋轉。順時針旋轉。BACEDhhh-1hh插入插入hhh-1h-1ABDCEhhh-1BCEADh1010先左后右雙旋轉先左后

7、右雙旋轉 (RotationLeftRight) (RotationLeftRight)n在結點在結點A的左子女的右子樹中插入新結點，的左子女的右子樹中插入新結點，該子樹高度增該子樹高度增1導致結點導致結點A的平衡因子變的平衡因子變?yōu)闉?2， 造成不平衡。造成不平衡。11 11插入插入hhACEDh-1h-1BFGE左單左單旋轉旋轉GACDBFhhh-1hn以結點以結點E為旋轉軸，將結點為旋轉軸，將結點B反時針旋轉，反時針旋轉，以以E代替原來代替原來B的位置。的位置。1212n再以結點再以結點E為旋轉軸，將結點為旋轉軸，將結點A順時針旋順時針旋轉。使之平衡化。轉。使之平衡化。右單右單旋轉旋轉A

8、EhhCDh-1hBFGFGDhAh-1CEBhh1313n在結點在結點A的右子女的左子樹中插入新結點，的右子女的左子樹中插入新結點，該子樹高度增該子樹高度增1。結點。結點A的平衡因子變?yōu)榈钠胶庖蜃幼優(yōu)?，發(fā)生了不平衡。發(fā)生了不平衡。n首先以結點首先以結點D為旋轉軸，將結點為旋轉軸，將結點C順時針順時針旋轉，以旋轉，以D代替原來代替原來C的位置。的位置。先右后左雙旋轉先右后左雙旋轉 (RotationRightLeft) (RotationRightLeft)1414插入插入hhh-1h-1ACEDBFG右單旋轉右單旋轉ACEBFGDhhhh-1n再以結點再以結點D為旋轉軸，將結點為旋轉軸，將

9、結點A反時針旋轉，反時針旋轉， 恢復樹的平衡?；謴蜆涞钠胶?。1515ACEDBFGhhh-1hhhh-1hACEBFGD1616AVLAVL樹的插入樹的插入n在向一棵本來是高度平衡的在向一棵本來是高度平衡的AVL樹中插入一樹中插入一個新結點時，如果樹中某個結點的平衡因子個新結點時，如果樹中某個結點的平衡因子的絕對值的絕對值 | bf | 1，則出現(xiàn)了不平衡，需要，則出現(xiàn)了不平衡，需要做平衡化處理。做平衡化處理。nAVL樹的插入算法從一棵空樹開始，通過輸樹的插入算法從一棵空樹開始，通過輸入一系列對象關鍵碼，逐步建立入一系列對象關鍵碼，逐步建立AVL樹。樹。n在插入新結點后，需從插入結點沿通向根的

10、在插入新結點后，需從插入結點沿通向根的路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結點，路徑向上回溯，如果發(fā)現(xiàn)有不平衡的結點，需從這個結點出發(fā)，使用平衡旋轉方法進行需從這個結點出發(fā)，使用平衡旋轉方法進行平衡化處理。平衡化處理。1717n設新結點設新結點p的平衡因子為的平衡因子為0，其父結點為，其父結點為pr。插。插入新結點后入新結點后pr的平衡因子值有三種情況：的平衡因子值有三種情況：n 結點結點pr的平衡因子為的平衡因子為0。說明剛才是在說明剛才是在pr的較的較矮的子樹上插入了新結點，此時不需做平衡化矮的子樹上插入了新結點，此時不需做平衡化處理，返回主程序。子樹的高度不變。處理，返回主程序。子樹的高度不

11、變。1.結點結點pr的平衡因子的絕對值的平衡因子的絕對值|bf| = 1。說明插入說明插入前前pr的平衡因子是的平衡因子是0，插入新結點后，以，插入新結點后，以pr為為根的子樹不需平衡化旋轉。但該子樹高度根的子樹不需平衡化旋轉。但該子樹高度10插入后prp1818增加，還需從結點增加，還需從結點pr向根方向回溯，繼續(xù)考向根方向回溯，繼續(xù)考查結點查結點pr雙親雙親(pr = Parent(pr)的平衡狀態(tài)。的平衡狀態(tài)。n 結點結點pr的平衡因子的絕對值的平衡因子的絕對值|bf| = 2。說明新說明新結點在較高的子樹上插入，造成了不平衡，結點在較高的子樹上插入，造成了不平衡，需要做平衡化旋轉。此時

12、可進一步分需要做平衡化旋轉。此時可進一步分2種情況種情況討論：討論：3. 若結點若結點pr的的bf = 2，說明右子樹高，結合，說明右子樹高，結合其右子女其右子女q 的的bf分別處理：分別處理：0-1 插入后prp1919若若q的的bf為為1，執(zhí)行左單旋轉。，執(zhí)行左單旋轉。若若q的的bf為為-1，執(zhí)行先右后左雙旋轉。，執(zhí)行先右后左雙旋轉。左單旋轉插入后2q1prp0pr0ppr=q右左雙旋轉插入后2q-1prp0pr0qpr=p2020 若結點若結點pr的的bf = -2，說明左子樹高，結合，說明左子樹高，結合其左子女其左子女q 的的bf分別處理：分別處理：若若q的的bf為為-1，執(zhí)行右單旋轉

13、；，執(zhí)行右單旋轉；若若q的的bf為為1，執(zhí)行先左后右雙旋轉。，執(zhí)行先左后右雙旋轉。n下面舉例說明在下面舉例說明在AVL樹上的插入過程。樹上的插入過程。-2q-1prp-2q1prp右單旋轉左右雙旋轉2121n例如，輸入關鍵碼序列為例如，輸入關鍵碼序列為 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和調整過程如下。插入和調整過程如下。160163- -10731600073110- -111637169000111163701273161190- -1- -2237112691601122222右左雙旋右左雙旋0左單旋左單旋18160073261190003160917

14、1126183- -1- -171614269111739182611162323151831816731171491615112626149從空樹開始的建樹過程從空樹開始的建樹過程2424AVLAVL樹的刪除樹的刪除n如果如果被刪結點被刪結點 x 最多只有一個子女，可做簡最多只有一個子女，可做簡單刪除單刪除:將將結點結點 x 從樹中刪去。從樹中刪去。因為結點因為結點 x 最多有一個子女，可以簡單地最多有一個子女，可以簡單地把把 x 的雙親中原來指向的雙親中原來指向 x 的指針改指到這的指針改指到這個子女結點；個子女結點；如果結點如果結點 x 沒有子女，沒有子女，x 雙親原來指向雙親原來指向

15、x的指針置為的指針置為 NULL。將原來以結點將原來以結點 x 為根的子樹的高度減為根的子樹的高度減 1。2525n如果如果被刪結點被刪結點 x 有兩個子女有兩個子女:搜索搜索 x 在中序次序下的在中序次序下的直接前驅直接前驅 y (同樣同樣可以找直接后繼可以找直接后繼)。把把結點結點 y 的內容傳送給結點的內容傳送給結點 x，現(xiàn)在問題，現(xiàn)在問題轉移到刪除轉移到刪除結點結點 y。把結點。把結點 y 當作被刪結當作被刪結點點x。因為結點因為結點 y 最多有一個子女，可以簡單最多有一個子女，可以簡單地用地用 1. 給出的方法進行刪除。給出的方法進行刪除。n必須沿結點必須沿結點 x 通向根的路徑反向

16、追蹤高度通向根的路徑反向追蹤高度的變化對路徑上各個結點的影響。的變化對路徑上各個結點的影響。2626n用一個布爾變量用一個布爾變量shorter（縮短）（縮短）來指明子來指明子樹高度是否被縮短。在每個結點上要做的樹高度是否被縮短。在每個結點上要做的操作取決于操作取決于 shorter的值和結點的的值和結點的bf，有時，有時還要依賴子女的還要依賴子女的bf。n布爾變量布爾變量shorter的值初始化為的值初始化為True。然后。然后對于從對于從x的雙親到根的路徑上的各個結點的雙親到根的路徑上的各個結點p，在在 shorter保持為保持為True時執(zhí)行下面操作。如時執(zhí)行下面操作。如果果 short

17、er變成變成False，算法終止。，算法終止。 當前結點當前結點 p 的的bf為為0。如果它的左子樹或如果它的左子樹或右子樹被縮短，則它的右子樹被縮短，則它的bf改為改為1或或-1，同，同時時 shorter置為置為False。2727刪除后不旋轉 結點結點 p 的的 bf 不為不為0且較高的子樹被縮短。且較高的子樹被縮短。則則 p 的的 bf 改為改為0，同時，同時shorter置為置為True。p0hhh-1p1hh-1刪除后不旋轉p-1hh-1p0h-1h-12828 結點結點 p 的的 bf 不為不為0，且較矮的子樹又被縮，且較矮的子樹又被縮短。短。則在結點則在結點 p 發(fā)生不平衡。需

18、要進行平發(fā)生不平衡。需要進行平衡化旋轉來恢復平衡。衡化旋轉來恢復平衡。令令 p 的較高的子樹的根為的較高的子樹的根為 q（該子樹未被（該子樹未被縮短），根據(jù)縮短），根據(jù) q 的的 bf，有如下，有如下 3 種平衡化種平衡化操作。操作。旋轉的方向取決于是結點旋轉的方向取決于是結點 p 的哪一棵子樹的哪一棵子樹被縮短。被縮短。2929 如果如果 q（較高的子樹）的（較高的子樹）的 bf 為為0，執(zhí)行一，執(zhí)行一個單旋轉來恢復結點個單旋轉來恢復結點 p 的平衡，置的平衡，置shorter為為False。無需檢查上層結點的平無需檢查上層結點的平衡因子。衡因子。左單旋轉1hh-1phq-11hhh-1ph

19、0q3030 如果如果 q 的的 bf 與與 p 的的 bf 相同，則執(zhí)行一個相同，則執(zhí)行一個單旋轉來恢復平衡，結點單旋轉來恢復平衡，結點 p 和和 q 的的 bf 均均改為改為0，同時置，同時置shorter為為True。還要繼續(xù)還要繼續(xù)檢查上層結點的平衡因子。檢查上層結點的平衡因子。左單旋轉0h-1h-1phq01hh-1h-1ph1q3131 如果如果 p 與與 q 的的 bf 相反，則執(zhí)行一個雙旋相反，則執(zhí)行一個雙旋轉來恢復平衡。先圍繞轉來恢復平衡。先圍繞 q 轉再圍繞轉再圍繞 p 轉。轉。新根結點的新根結點的 bf 置為置為0，其他結點的，其他結點的 bf 相相應處理，同時置應處理，

20、同時置shorter為為True。0h-1h-1h-1h-100pqr右左雙旋轉高度減11hh-1p- -1qh-1或h-2h-1或h-2h-1r3232ABCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111樹的初始狀態(tài)樹的初始狀態(tài)舉例舉例3333刪除結點刪除結點P尋找結點尋找結點P的中序直接前驅的中序直接前驅O, 用用O頂替頂替P, 刪除刪除O。ABCDEFGHIJKLMNOPQRST0000000- -1- -1- -1- -1- -1- -1- -111111用用O取代取代P3434刪除結點刪除結點PABCDEFGHIJKLMNOQRST000000- -1- -1- -1- -1- -1- -1- -111111左單旋轉左單旋轉O與與R的平衡因子同號的平衡因子同號, 以以R為旋轉軸做左單旋轉為旋轉軸做左單旋轉, M的子樹高度減的子樹高度減 1。3535刪除結點刪除結點PM的子樹高度減的子樹高度減 1，M發(fā)生不平衡。發(fā)生不平衡。M與與E的平的平衡因子反號衡因子反號, 做左右雙旋轉。做左右雙旋轉。ABCDEFGHIJKLMNOQRST000000- -1- -1- -1- -1- -1- -1- -1