AVL高度平衡二元搜尋樹介紹 - 筆記長也

AVL高度平衡二元搜尋樹介紹

2018-01-14 20:16:00   資料結構

    今天要來介紹AVL樹,AVL樹是一種高效二元搜尋樹,一般的二元搜尋樹在極端狀況下,可能會退化成鏈。

    這會使得搜尋時間花費增加,根據E = I +2n(這裡不寫推導過程),我們得知當樹為歪斜樹的時候E的值會是最大,而這會使得搜尋一顆樹的花費時間也最大。

    因此,AVL樹即是透過頻繁旋轉來維持這顆樹擁有最小花費。

    AVL樹中,新增節點時,會檢查路徑上根節點左子樹及右子樹的深度

    當兩邊深度差達到2時就會進行旋轉(代表某邊過重)

    平衡因子為左子樹深度減去右子樹深度,當平衡因子達到2或-2 就會進行旋轉

    其中共有四種情形: LL , LR , RR , RL

    第一個字母代表哪邊子樹過重,第二個字母代表是在該子樹中哪邊添加節點導致不平衡

    一.左子樹過重:

    1.在左子樹的左子增加節點  (LL)

   

    2.在左子樹的右子增加節點  (LR)

                                                                                               

    二.右子樹過重:

    3.右子樹的右子增加節點  (RR)

   

    4.右子樹的左子增加節點  (RL)
   

    而AVL樹節點的刪除可以直接採用一般二元搜尋樹的方式,只需要在刪除後繼續檢查平衡因子維持即可。

    此外,AVL樹的節點結構一般會將平衡因子放入結構中,不過如此一來會增加實做上的複雜性,因此建議可以每次檢查時直接用函式檢測深度即可。因為AVL樹為高度平衡二元樹,會儘量維持不使樹的深度過大,如此一來檢測深度時的時間花費也不會太高。

關於作者