????最近比較忙浪腐，沒閑得下時間寫簡書禾锤。小編在之前的分享中有講過二叉搜索樹，如下的兩顆樹都滿足二叉搜索樹的條件刷允。
? ? 圖片1中兩棵二叉搜索樹都通過前面小編分享的代碼進行構造冤留”棠遥可發(fā)現(xiàn)二叉搜索樹有一個缺點就是，樹的結構是無法預料的纤怒，隨意性很大糯而，它只與節(jié)點的值和插入的順序有關系，往往得到的是一個不平衡的二叉樹肪跋。在最壞的情況下歧蒋，可能得到的是一個單支二叉樹，如上圖1所示州既，其高度和節(jié)點數(shù)相同谜洽，相當于一個單鏈表，對其正常的時間復雜度有O(lgn)變成了O(n)吴叶，從而喪失了二叉排序樹的一些應該有的優(yōu)點【對于該部分時間復雜度的分析阐虚，可看下小編之前分享的另一篇簡書】。
????因此我們需要一種算法蚌卤，能夠改進在樹上的查找实束、插入和刪除等速率。G.M. Adelson-Velsky和 E.M. Landis率先發(fā)明了這樣的一種樹逊彭，也就是自平衡二叉查找樹【Self-Balancing Binary Search Tree,簡稱平衡二叉樹咸灿，AVL樹的名字來源于它的發(fā)明作者】。平衡二叉樹是對普通的二叉搜索樹的改進侮叮，因此它一定滿足二叉搜索樹的所有條件避矢，且平衡二叉樹是基于二分法的策略提高數(shù)據(jù)的查找速度的二叉樹的數(shù)據(jù)結構。
? ??平衡二叉樹具備的兩個特點：
????① 它必須是二叉查找樹
????② 它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超過1囊榜，且它的左子樹和右子樹都是一顆平衡二叉樹审胸。
????接下來小編先簡單介紹幾個有關AVL樹的概念。
????（1）平衡因子
????將二叉樹上節(jié)點的左子樹高度減去右子樹高度的值稱為該節(jié)點的平衡因子BF（Balance Factor）卸勺。我們來看下圖：
? ??在該AVL樹上：
????節(jié)點60的左子樹高度為2砂沛，右子樹高度為2，BF=2-2?= 0曙求；
????節(jié)點45的左子樹高度為1碍庵，右子樹高度為0，BF=1-0= 1悟狱；
????節(jié)點32的左子樹高度為0怎抛，右子樹高度為0，BF= 0-0 = 0芽淡；
????節(jié)點65的左子樹高度為0马绝，右子樹高度為1，BF= 0-1 = -1挣菲；
????對于平衡二叉樹富稻，BF的取值范圍為[-1,1]掷邦。如果發(fā)現(xiàn)某個節(jié)點的BF值不在此范圍，則需要對樹進行調整椭赋。
????（2）最小不平衡樹
????距離插入節(jié)點最近的抚岗，且平衡因子的絕對值大于1的節(jié)點為根的子樹.，我們稱之為最小不平衡樹哪怔。我們在上圖中插入一個節(jié)點42得到下圖的樹：
? ??其中宣蔚，我們管32為插入節(jié)點，以節(jié)點32為樹根的子樹的BF=1认境，以節(jié)點45為樹根的子樹的BF=2胚委，大于1。因此要對該樹進行調整叉信，該樹稱之為最小不平衡樹亩冬。
????因此，對于一棵不平衡樹的節(jié)點硼身，我們可以定義這么一個類來表示【后續(xù)代碼添加還會對該類進行修改】硅急，截圖如下：
? ??在類中定義節(jié)點的高度后續(xù)可用來計算節(jié)點的平衡因子BF。那如何對建立的二叉搜索樹實時進行調整呢佳遂，我們來看看幾種情況营袜。
????（1）LL型調整
????首先我們來看一個最簡單的例子，如下圖4中的①丑罪。這是一棵簡單的平衡二叉樹连茧，插入節(jié)點C得到的樹的形狀如②所示。這個時候節(jié)點A的平衡因子BF=2巍糯，大于1，因此樹不平衡了客扎，需要調整祟峦。當然要注意調整完的樹也必須是二叉搜索樹。這個時候徙鱼，最小的失衡子樹為以根節(jié)點為A的樹宅楞。以該失衡節(jié)點A的左孩子節(jié)點B為固定的軸進行旋轉。在下圖中袱吆，我們將A繞B進行順時針旋轉厌衙，也就是右旋。得到的樹的形狀如③所示绞绒。這個時候B為根節(jié)點婶希，且滿足B的鍵值大于C的鍵值，B的鍵值小于A的鍵值蓬衡，滿足二叉搜索樹的特征喻杈。
????當然上圖是比較簡單的情況彤枢，如果是下面的情況，還需進行其它操作筒饰。
????在圖片5中的①缴啡，是一棵平衡二叉樹，插入新節(jié)點F后瓷们，根節(jié)點A的左子樹高度為3业栅，右子樹高度為1，BF=3-1=2>1谬晕，因此需要進行調整碘裕。其失衡節(jié)點為根節(jié)點A，以A的左孩子節(jié)點為軸進行旋轉固蚤。使得以A為根節(jié)點的右子樹成為節(jié)點B的右子樹娘汞，也就是讓A成為B的右孩子。因為節(jié)點B存在右子樹夕玩，需讓該右子樹成為節(jié)點A的左子樹你弦，即讓D成為A的左孩子。
????所以所謂的LL型調整意思就是在最小失衡子樹的左孩子的左子樹上插入了新的結點燎孟。下圖是通用的LL型調整的圖禽作。
? ??在該圖片6中的①，A的左子樹高度為h+1揩页，B的子樹的高度為h旷偿。插入新節(jié)點后，A的左子樹高度為h+2爆侣。先找到最小失衡子樹的根A萍程，以其左孩子結點B為軸，對不平衡結點A進行順時針旋轉（也稱右旋）兔仰。右旋是讓B頂替A的位置茫负，并置A為B的右孩子，如果B存在右子樹BR乎赴，則置BR為A的左子樹忍法。
????該部分代碼截圖如下：
? ? 小編這里提醒下，上圖中用了空格+"\"進行換行榕吼，實則這是一個條件判斷語句饿序。
? ??（2）RR型調整
? ? 在A的右孩子(R)的右子樹(R)上插入新結點，使原來平衡二叉樹變得不平衡羹蚣，此時A的平衡因子由-1變?yōu)?2原探。下圖是RR型的最簡單形式。
????顯然，按照大小關系踢匣，結點B應作為新的根結點告匠，其余兩個節(jié)點分別作為左右孩子節(jié)點才能平衡，A結點就好像是繞結點B逆時針旋轉【左旋】一樣离唬。
? ? 這邊來繼續(xù)看一個最小平衡樹應該注意的事項后专，通過下面的例子來看看。
? ? 在圖片8中输莺，在?①所示的二叉樹中插入鍵值為7的節(jié)點戚哎，得到②。很明顯這是一棵非平衡二叉樹嫂用。從鍵值為7這個插入節(jié)點往上看型凳，發(fā)現(xiàn)對于鍵值為5的節(jié)點，其平衡因子BF=-2嘱函。故以該節(jié)點為根節(jié)點的樹為最小非平衡二叉樹甘畅，對其進行調整，最后得到③所示的平衡二叉樹往弓。
????對于RR型疏唾，正好與LL型對稱，對以A為根的最小失衡子樹進行逆時針旋轉（也稱左旋)函似，如圖所示槐脏。
????RR型調整，表示在A的右孩子B的右子樹BR（不一定為空）中插入結點【圖中陰影部分所示】而導致不平衡（h表示子樹的深度）撇寞。
????這種情況調整如下：
????① 將A的右孩子B提升為新的根結點
????② 將原來的根結點A降為B的左孩子
????③ 各子樹按大小關系連接（AL和BR不變顿天，BL調整為A的右子樹）
? ? 代碼截圖如下：
? ??（3）LR型調整
????由于在A的左孩子(L)的右子樹(R)上插入新結點，使原來平衡二叉樹變得不平衡蔑担，此時A的平衡因子由1變?yōu)?牌废。總之啤握，LR型指的是最小失衡子樹的左孩子的右子樹上插入了新的結點鸟缕。處理辦法為，首先找到以A為根的最小失衡子樹恨统，以該子樹的左孩子結點B為軸，對右子樹結點C進行左旋調整三妈，使之變?yōu)長L型畜埋。再以C為軸，對不平衡結點A進行右旋調整畴蒲。
????我們先來看看最簡單的例子悠鞍。
????在上圖片9中的①，B的右子樹上插入新節(jié)點C后，得到②咖祭。此時節(jié)點A的BF=2掩宜，需要對該樹進行調整。由于調整后的樹必須滿足二叉搜索樹的特征么翰，故應將C作為根節(jié)點牺汤，B作為左孩子，A為右孩子浩嫌。調整后的樹的形狀如③所示檐迟。
????來看看下面的比較復雜的實例。
? ??在圖片10中的①這棵樹码耐，插入鍵值7追迟，得到②。這是一棵非平衡樹骚腥，需要進行調整敦间。首先找到以鍵值8為根的最小失衡子樹，以該子樹的左孩子結點（鍵值為5）為軸束铭，對右子樹結點（鍵值為6）進行左旋調整（RR型調整）廓块，使之變?yōu)長L型，得到圖③纯露。以鍵值為8的根節(jié)點的左孩子節(jié)點（鍵值為6）為軸進行旋轉剿骨。使得以鍵值為8的根節(jié)點的右子樹成為鍵值為6的節(jié)點的右子樹。因為鍵值為6的節(jié)點存在右子樹埠褪，需讓該右子樹成為鍵值為8的節(jié)點的左子樹浓利，調整后得到圖④。
????下面是一般的LR型調整的變化圖钞速。
????LR型調整的一般形式贷掖，表示在A的左孩子B的右子樹【根結點為C，不一定為空)中插入結點(圖中兩個陰影部分之一)而導致不平衡（h表示子樹的深度）】渴语。
????這種情況調整如下
????①將B的左孩子C提升為新的根結點苹威；
????②將原來的根結點A降為C的右孩子；
????③各子樹按大小關系連接（BL和AR不變驾凶，CL和CR分別調整為B的右子樹和A的左子樹）
? ? 代碼截圖如下：
（4）RL型調整
????RL型指的是最小失衡子樹的右孩子的左子樹上插入了新的結點牙甫。RL型和LR型對稱，需依次進行右旋處理和左旋處理调违，如圖所示窟哺。
????總的失衡調整圖如下所示：
????RL型調整的一般形式如上圖所示，表示在A的右孩子B的左子樹【根結點為C技肩，不一定為空)中插入結點(圖中兩個陰影部分之一)而導致不平衡（h表示子樹的深度）】且轨。
????這種情況調整如下：
????① 將B的左孩子C提升為新的根結點；
????② 將原來的根結點A降為C的左孩子；
????③ 各子樹按大小關系連接（AL和BR不變旋奢，CL和CR分別調整為A的右子樹和B的左子樹）
????代碼截圖如下：
????注意的是泳挥，在構造平衡二叉樹的過程中，經(jīng)常要使用遞歸的方法至朗，找到最小非平衡二叉樹對其進行調整屉符，上面圖示的四種調整方法要靈活應用。
? ? 代碼主體來源于網(wǎng)上爽丹，小編只是進行部分查錯修改筑煮、注釋、以及優(yōu)化粤蝎。代碼截圖如下：
? ? 關于平衡二叉樹的查找真仲，插入，刪除等時間復雜度初澎，可看看小編之前分享的另一篇文章秸应，用相同的方法去分析，小編這里不做過多的分析解釋碑宴。
