在講到集合的時(shí)候，很容易讓人想到的是數(shù)組和鏈表。然后大家會(huì)討論這兩種數(shù)據(jù)結(jié)構(gòu)的差異。但是根據(jù)指定的內(nèi)容在集合中查找，這兩種數(shù)據(jù)結(jié)構(gòu)的性能卻沒(méi)有區(qū)別都是O(n)，如何提高在集合中檢索指定內(nèi)容數(shù)據(jù)的性能，是我們?cè)诔绦蜷_(kāi)發(fā)中面臨的問(wèn)題。
平衡二叉樹(shù)(AVL樹(shù))
通過(guò)[二叉排序樹(shù)及相關(guān)操作說(shuō)明][1]我們可以總結(jié)二叉排序樹(shù)的形狀是由根節(jié)點(diǎn)的值決定的，如果在極端情況下，根節(jié)點(diǎn)的值取的足夠小，容易退化成鏈表，導(dǎo)致查詢時(shí)間復(fù)雜度升高，查詢性能下降。
因此在二叉排序樹(shù)的基礎(chǔ)上具有以下性質(zhì)的二叉排序樹(shù)稱為二叉平衡樹(shù)：
1. 左右子樹(shù)的深度絕對(duì)值不超過(guò)1
2. 左右子樹(shù)分別都是平衡二叉樹(shù)
術(shù)語(yǔ)說(shuō)明及圖例
AVL樹(shù)最明顯的特點(diǎn)是根據(jù)其特性能進(jìn)行旋轉(zhuǎn)，但是在描述旋轉(zhuǎn)的時(shí)候，一些術(shù)語(yǔ)比較晦澀難懂，所以對(duì)一些術(shù)語(yǔ)進(jìn)行了圖形描述
1. 根節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)的左子樹(shù)
2. 根節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)的右子樹(shù)
3. 根節(jié)點(diǎn)的右子樹(shù)的根節(jié)點(diǎn)的左子樹(shù)
4. 根節(jié)點(diǎn)的右子樹(shù)的根節(jié)點(diǎn)的右子樹(shù)
樹(shù)的深度
樹(shù)中結(jié)點(diǎn)的最大層次結(jié)點(diǎn)為樹(shù)的深度
平衡因子
Balance Factory=> BF定義為該結(jié)點(diǎn)的左子樹(shù)的深度減去該結(jié)點(diǎn)的右子樹(shù)的深度，則平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1。只要二叉樹(shù)上的一個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹(shù)就是不平衡的。
平衡二叉樹(shù)(AVL樹(shù))的旋轉(zhuǎn)
AVL樹(shù)的插入操作和刪除操作都有可能造成AVL二叉樹(shù)失去其原有的特性，為此需要進(jìn)行旋轉(zhuǎn)操作使AVL樹(shù)再平衡
說(shuō)明：為了對(duì)比平衡二叉樹(shù)旋轉(zhuǎn)前后的變化，我沒(méi)有做節(jié)點(diǎn)名稱的變化
-
單向右旋平衡處理
在平衡二叉樹(shù)的根節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)的左子樹(shù)上插入一個(gè)節(jié)點(diǎn)導(dǎo)致二叉樹(shù)失去平衡，進(jìn)行的單向右旋平衡處理，操作如圖所示：單向右旋平衡處理 -
單向左旋平衡處理
在平衡二叉樹(shù)的根節(jié)點(diǎn)的右子樹(shù)的根節(jié)點(diǎn)的右子樹(shù)上插入一個(gè)節(jié)點(diǎn)導(dǎo)致平衡二叉樹(shù)失去平衡，進(jìn)行的單向左旋平衡處理，操作如圖所示：單向左旋處理 -
雙向旋轉(zhuǎn)，先左旋后右旋平衡處理
在平衡二叉樹(shù)的根節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)的右子樹(shù)上插入一個(gè)節(jié)點(diǎn)導(dǎo)致平衡二叉樹(shù)失去平衡，進(jìn)行的雙向旋轉(zhuǎn)處理，操作如圖所示：雙向旋轉(zhuǎn)，先左旋后右旋平衡處理 -
雙向旋轉(zhuǎn)，先右旋再左旋平衡處理
在平衡的二叉樹(shù)的根節(jié)點(diǎn)的右子樹(shù)的根節(jié)點(diǎn)的左子樹(shù)上插入一個(gè)節(jié)點(diǎn)導(dǎo)致平衡二叉樹(shù)失去平衡，進(jìn)行的雙向旋轉(zhuǎn)處理，操作如圖所示：雙向旋轉(zhuǎn)，先右旋再左旋平衡處理
AVL樹(shù)旋轉(zhuǎn)總結(jié)
- 在平衡的二叉排序樹(shù)BBST(Balance Binary Sorted Tree)上插入一個(gè)新的數(shù)據(jù)元素e，平衡算法可描述如下：
- 若BBST是空樹(shù)，則插入一個(gè)數(shù)據(jù)元素e的新結(jié)點(diǎn)作為BBST的根節(jié)點(diǎn)，樹(shù)的深度增加1；
- 若數(shù)據(jù)元素e的關(guān)鍵字和BBST樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字相等，則查找成功，不進(jìn)行插入操作；
- 若數(shù)據(jù)元素e的關(guān)鍵字小于BBST樹(shù)的根節(jié)點(diǎn)的關(guān)鍵字，而且在BBST的左子樹(shù)中不存在和數(shù)據(jù)元素e的關(guān)鍵字相同的關(guān)鍵字，則將e插入BBST的左子樹(shù)上，若插入新元素之后的左子樹(shù)的深度增加(+1)時(shí)，需要分情況討論：
- 若BBST的左子樹(shù)的根結(jié)點(diǎn)的平衡因子為1，那么就進(jìn)行單向右旋進(jìn)行平衡處理，并且單向右旋處理后，將修改BBST樹(shù)的根結(jié)點(diǎn)及根結(jié)點(diǎn)的左右子樹(shù)根結(jié)點(diǎn)的平衡因子，BBST樹(shù)的深度保持不變；
- 若BBST的左子樹(shù)的根結(jié)點(diǎn)的平衡因子為-1，那么就進(jìn)行雙向旋轉(zhuǎn)，先左旋再右旋平衡處理，并且旋轉(zhuǎn)平衡處理之后修改BBST根結(jié)點(diǎn)及根結(jié)點(diǎn)左右子樹(shù)的根結(jié)點(diǎn)的平衡因子，樹(shù)的深度保持不變；
- 若數(shù)據(jù)元素e的關(guān)鍵字大于BBST樹(shù)的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的右子樹(shù)中不存在和數(shù)據(jù)元素e的關(guān)鍵字相同的關(guān)鍵字，則將e插入到BBST樹(shù)的右子樹(shù)上，參照第3步操作，分情況進(jìn)行討論針對(duì)不同情況進(jìn)行單向左旋平衡處理、雙向選裝，先右旋再左旋平衡處理。
- 當(dāng)平衡二叉排序樹(shù)失去平衡時(shí)，僅需要對(duì)平衡因子絕對(duì)值大于1的結(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)進(jìn)行調(diào)整即可，且調(diào)整以后二叉排序樹(shù)的深度保持不變。
