<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # AVL Tree - AVL二叉樹 -------- #### AVL二叉平衡樹 AVL樹是最早發明的一種自平衡二叉查找樹，樹中的任何節點的左右兩個子樹的高度最大差別為$$ 1 $$，因此也稱為高度平衡樹。包含$$ n $$個節點的AVL樹其查找、插入、刪除操作的平均時間復雜度都是$$ O(log_{2}?n) $$。AVL樹高度為$$ O(log_{2}?n) $$。 引入二叉樹上節點之間距離和高度的定義。一個葉子節點向上到達根節點所經過的跳數為這兩個節點的距離，一個節點和自己的距離為$$ 0 $$，將空節點的高度視作$$ -1 $$。根節點到達其所有葉子節點的最大距離即為根節點的高度，同時也是該子樹的高度。顯然對于任意節點都有： $$ height_{x} = max(height_{left}, height_{right}) + 1 $$ 一個節點的左右孩子的高度差為該節點的平衡因子： $$ factor = height_{left} - height_{right} $$ 當一個節點的$$ \lvert factor \rvert \leq 1 $$時稱該節點所在的子樹是平衡的，否則是不平衡的。 除了基本的二叉查找樹屬性，AVL樹擁有以下屬性： $$ (1) $$ AVL樹上所有節點都是平衡的，即平衡性； $$ (2) $$ AVL樹的高度為根節點的高度； $$ (3) $$ AVL樹的高度為$$ height = O(log_2 n) $$； AVL樹的查詢操作和二叉查找樹一樣，插入/刪除操作也基本相同，首先通過二分查找找到合適插入的位置/要被刪除的節點，然后做插入/刪除操作。插入/刪除會破壞AVL樹的平衡性，LL（單向右旋平衡處理/左左）、RR（單向左旋平衡處理/右右）、LR（先左后右雙向旋轉平衡處理/左右）、RL（先右后左雙向旋轉平衡處理/右左）四種情況是所有需要調整的情況：     上面四種情況包含了所有從不平衡轉化為平衡。通過節點的高度值、該節點是其父結點的左或者右，可以判斷節點屬于哪種情況，做相應的操作。 對于下面這個AVL樹，每個節點中上面的數字是節點下標，下面的數字是該節點的高度值$$ height $$。將$$ 18 $$從該AVL樹的根節點開始，按照二分查找算法依次經過節點$$ 10 \rightarrow 15 \rightarrow 19 \rightarrow 16 \rightarrow 17 $$，最后插入$$ 17 $$的右孩子節點；  新節點插入完成后，我們沿著父結點指針一路向上，檢查每個節點是否平衡，若不平衡則進行旋轉操作，再更新節點高度，直到根節點。  $$ (1) $$ 節點$$ 18 $$為葉子節點，因此高度值為$$ height_{18} = 0 $$；  $$ (2) $$ 平衡因子為$$ factor_{17} = \lvert height_{nil} - height_{18} \rvert = \lvert - 1 - 0 \rvert = 1 $$，不需要旋轉，更新節點$$ 17 $$的高度值$$ height_{17} = max?(height_{nil},height_{nil}) + 1 = max?(-1,0) + 1 = 1 $$；   $$ (3) $$ 平衡因子為$$ factor_{16} = \lvert height_{nil} - height_{17} \rvert = \lvert - 1 - 1 \rvert = 2 \gt 1 $$，需要進行RR操作，旋轉后節點$$ 16 $$的高度值為$$ height_{16} = 0 $$，更新節點$$ 16 $$的高度值$$ height_{16} = max?(height_{nil},height_{17}) + 1 = max?(-1,1) + 1 = 2 $$；  $$ (4) $$ 平衡因子為$$ factor_{19} = \lvert height_{17} - height_{20} \rvert = \lvert 1 - 0 \rvert = 1 $$，更新節點$$ 19 $$的高度值$$ height_{19} = max?(height_{16},height_{20}) + 1 = max?(1,0) + 1 = 2 $$；  $$ (5) $$ 平衡因子為$$ factor_{15} = \lvert height_{13} - height_{19} \rvert = \lvert 1 - 2 \rvert = 1 $$，更新節點$$ 15 $$的高度值$$ height_{15} = max?(height_{13},height_{19}) + 1 = max?(1,2) + 1 = 3 $$；  $$ (6) $$ 平衡因子為$$ factor_{10} = \lvert height_{5} - height_{15} \rvert = \lvert 2 - 3 \rvert = 1 $$，更新節點$$ 10 $$的高度值$$ height_{10} = max?(height_{5},height_{15}) + 1 = max?(2,3) + 1 = 4 $$； AVL樹的刪除操作和BinarySearchTree一樣： $$ (1) $$ 若$$ x $$為葉子節點，既沒有左孩子節點也沒有右孩子節點，直接刪除； $$ (2) $$ 若$$ x $$只有一個孩子節點$$ y $$，則像鏈表一樣將$$ x $$從其父節點和$$ y $$之間刪除； $$ (3) $$ 若$$ x $$同時有左右孩子節點，按照中序遍歷找出二叉樹中比$$ x $$大的下一個節點$$ next $$（中序遍歷下的后繼節點），用其值代替$$ x $$，實際刪除節點$$ next $$； 刪除完成后從$$ x $$的父節點開始依次向上，檢查每個節點是否平衡，若不平衡則進行旋轉操作，再更新節點高度，直到根節點。檢查本身的時間復雜度為$$ O(log_2 n) $$。下圖中刪除節點$$ 15 $$，節點$$ 15 $$的中序遍歷后繼節點$$ 16 $$代替它，然后刪除真正的$$ 16 $$。從新的$$ 16 $$開始檢查每個節點是否平衡，直到根節點。本次刪除結束。 AVL樹的插入/刪除操作的實際操作需要約$$ O(2 \times log_2 n) $$次，其中$$ O(log_2 n) $$花費在從根節點向下尋找合適的插入位置/要被刪除的節點，$$ O(log_2 n) $$花費在插入/刪除完成后向上對每個節點的檢查以及旋轉操作。  -------- #### AVL Tree * https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ * https://www.geeksforgeeks.org/avl-tree-set-2-deletion/ -------- #### 源碼 [AvlTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/AvlTree.h) [AvlTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/AvlTree.cpp) #### 測試 [AvlTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/AvlTreeTest.cpp)