7.6.平衡二叉樹(英文縮寫為AVL樹)

一.平衡二叉樹的定義：

1.平衡二叉樹簡稱平衡樹(AVL樹，該縮寫來源于平衡二叉樹的發明人的名字簡稱)；

2.結點的平衡因子=左子樹高-右子樹高；

3.以上述圖片左下角的二叉樹為例，結點50的左子樹的高度為2，右子樹的高度為3，因此結點50的平衡因子為2-3即-1；

4.顯然如果一棵二叉樹是平衡的，那么各個結點的平衡因子只可能是-1、0、1，也就是絕對值不超過1，如果二叉樹中有任何一個結點的平衡因子絕對值超過1，那么這棵二叉樹一定不是平衡二叉樹；

5.在平衡二叉樹結點的結構體中可以新增一個參數int balance記錄平衡因子，如下：

#include<stdio.h>
?
//平衡二叉樹結點
typedef struct AVLNode
{int key; ? ? ?//結點的數據域，該變量的類型不固定，因題而異int balance; ?//平衡因子struct AVLNode *lchild,*rchild; //結點的左孩子指針、右孩子指針 ?
}AVLNode,*AVLTree; //AVLNode代表平衡二叉樹的結點，*AVLTree代表平衡二叉樹 
?
int main()
{return 0;
}

6.之前說過，如果使一棵二叉排序樹保持平衡，就可以保證這棵二叉排序樹的查找效率達到O(log?n)即查找效率達到最好，因此要重點研究在插入一個新結點之后，如何保持二叉樹的平衡。

二.平衡二叉樹的插入：

實例：

以上述圖片左邊的二叉排序樹為例，

現在插入關鍵字為67的結點，根據二叉排序樹的特性可得知插入的具體位置在關鍵字為68的結點的左子樹上，

新插入關鍵字為67的結點的所有祖先的平衡因子都受到了影響，

現在要讓二叉排序樹中每一個結點恢復平衡的方法就是可以從新插入的結點開始往上找，找到第一個不平衡的結點

->本例中從關鍵字為67的結點想上找第一個不平衡的結點是關鍵字為70的結點，該結點的平衡因子為2，它是距離新插入的結點67第一個不平衡的結點，現在可以把以關鍵字為70的結點作為根結點的子樹稱為"最小不平衡子樹"，之所以稱為最小，是因為如果繼續往上找，第二個不平衡的結點是關鍵字為66的結點，以這個結點為根結點的子樹顯然要更大，實際中只需要調整這棵"最小不平衡子樹"即可。

調整的效果如下圖：

具體的調整規則之后探討，只需要知道把這棵"最小不平衡子樹"恢復平衡之后，其他的祖先結點就都恢復了平衡，

所以當插入一個新結點之后導致不平衡的話，只需要調整"最小不平衡子樹"就可以讓其他結點恢復平衡。

三.調整"最小不平衡子樹"->LL和RR：

分為四種情況，分別是LL、RR、LR、RL：

1.LL：在A結點的左孩子的左子樹中插入新結點導致A結點不平衡->需要右旋

以上述圖片為例，

灰色方形的框表示結點的子樹，該子樹的高度用H表示，其中這些子樹都是平衡的
BL表示B結點的左子樹，BR表示B結點的右子樹，AR表示A結點的右子樹

最左邊的二叉樹中A結點的左子樹是以B結點為根結點的樹，其中BL的高度為H，BR的高度也為H，算上B結點，根據二叉樹的定義可知以B結點為根結點的樹的高度為H+1（加的1是B結點的高度），A結點的右子樹是AR，高度為H，

所以A結點的平衡因子=(H+1)-H=1，所以A結點是平衡的；B結點的平衡因子=H-H=0，所以B結點是平衡的；

此時在A結點的左孩子即B結點的左子樹BL中插入一個新結點（上述圖片中間的二叉樹），會導致A結點不平衡，這是因為B結點的左子樹BL變高了，BL的高度變為了H+1，所以A結點的左子樹整體來看高度變為了H+2，而A結點的右子樹AR的高度仍保持為H，所以此時A結點的平衡因子=(H+2)-H=2，導致A結點不平衡；B結點的平衡因子=(H+1)-H=1，所以B結點是平衡的，

（注：假定以A結點為根結點的二叉樹就是最小不平衡子樹）

因此需要調整以A結點為根結點的二叉樹（即上述圖片中最中間的二叉樹）使其保持平衡，

如下圖：

如上圖，

要調整以A結點為根結點的二叉樹即"最小不平衡子樹"（即上述圖片中最中間的二叉樹）使其平衡，

調整的結果需要滿足：

恢復"最小不平衡子樹"的平衡
使得"最小不平衡子樹"在調整之后依然滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"

在本例中結點的大小關系為BL<B<BR<A<AR（注：以A結點為根結點的二叉樹是二叉排序樹，在A結點的左子樹中的每一個結點的值都小于結點A的值，比如BR<A，B<A），

使得以A結點為根結點的二叉樹即"最小不平衡子樹"恢復平衡的處理方法如下：

步驟一：讓B結點右旋->具體的做法就是讓B結點向右上旋轉代替A結點成為該二叉樹的根結點，B結點的右子樹就是以A結點為根結點的樹；

步驟二：處理子樹BL、BR、AR->

首先看子樹BL，BL之前是B結點的左子樹，BL的值小于B結點值(BL<B)，所以只能把BL連接在B結點的左子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹BR，BR之前是B結點的右子樹，現在B結點的右子樹已經掛了A結點，那么BR就不能作為B結點的右子樹了，但是有BR的值小于A結點的值(BR<A)，所以可以把子樹BR當作A結點的左子樹
最后看子樹AR，AR之前是A結點的右子樹，有AR的值大于A結點的值(A<AR)，所以AR繼續作為A結點的右子樹

這樣就可以既保證二叉排序樹的特性，同時BL這個部分的高度是H+1即成功插入了新結點，

經過上述的調整之后(上述圖片最右邊的樹)B結點的左子樹BL的高度為H+1、右子樹的高度為H+1，即B結點的平衡因子=(H+1)-(H+1)=0，

A結點的左子樹BR的高度為H、右子樹AR的高度為H，即A結點的平衡因子=H-H=0，

可知以A結點為根結點的子樹和以B結點為根結點的子樹都保持了平衡，

這樣一來就可以讓"最小不平衡子樹"恢復平衡，同時又保持二叉排序樹的特性。

Ⅰ.思考1：

為什么要假定所有灰色方形的框表示的子樹的高度都是H呢，那有沒有其他的情況？

首先看上述圖片中最左邊的樹的AR，A結點的右子樹AR假設高度為H，如果AR高度改為H+1，由于A結點的左子樹的高度也為H+1，所以此時A結點的平衡因子=(H+1)-(H+1)=0，A結點是平衡的

這種情況下在BL插入一個新結點，BL的高度變為H+1，所以A結點左子樹的高度為H+2，A結點的右子樹的高度為H+1，那么A結點平衡因子=(H+2)-(H+1)=1，此時A結點是平衡的，就不會出現所需要探討的不平衡的情況，所以A結點右子樹的高度一定是H，而不是H+1。

Ⅱ.思考2：

為什么要假定所有灰色方形的框表示的子樹的高度都是H呢，那有沒有其他的情況？

首先看上述圖片中最左邊的樹的AR，A結點的右子樹AR假設高度為H，如果AR高度改為H-1，由于A結點的左子樹的高度為H+1，所以此時A結點的平衡因子=(H+1)-(H-1)=2，使得A結點一開始就是不平衡的，而現在要探討的是插入一個新結點后才導致A結點不平衡，與題目要求違背了。

Ⅲ.思考3：

為什么要假定所有灰色方形的框表示的子樹的高度都是H呢，那有沒有其他的情況？

首先看上述圖片中最左邊的樹的BR，B結點的右子樹BR假設高度為H，如果BR高度改為H-1，由于B結點的左子樹BL的高度為H，所以此時B結點的平衡因子=H-(H-1)=1，可知B結點是平衡的，滿足平衡二叉樹的條件，

但是在這種情況下，如果B結點的左子樹BL添加一個結點后高度變為H+1，這時B結點的平衡因子=(H+1)-(H-1)=2，導致B結點不平衡，這樣的話B結點就是距離新插入的結點最近的不平衡點，所以以B結點為根結點的樹就是"最小不平衡子樹"了，但現在研究的是以A結點為根結點的樹是"最小不平衡子樹"，所以B結點的右子樹BR的高度不可能是H-1，而是H->其他的情況同理，自行推理。

總之，在這個地方只要假定某一個灰色方形的框表示的子樹的高度是H的話，那其他的灰色方形的框表示的子樹的高度也必須是H，只有這樣才能在LL處插入新結點后導致A結點是為"最小不平衡子樹"的根結點。

2.LL的代碼實現：

以上述圖片中的二叉排序樹為例，

f指針(father的縮寫)指向A結點即f指針表示A結點；A結點的左子樹為f->lchild；A結點的右子樹為f->rchild（注：f指針始終指向A結點，不會改變）
p指針指向B結點即p指針表示B結點；B結點的左子樹為p->lchild；B結點的右子樹為p->rchild（注：p指針始終指向B結點，不會改變）
gf指針(grandfather的縮寫)指向整個二叉樹的根結點的父結點；由于整個二叉樹的根結點可能是其父結點的左孩子，也可能是右孩子，所以整個二叉樹的根結點既可能是gf->lchild，也可能是gf->rchild，因此gf->lchild或gf->rchild就表示整個二叉樹的根結點（注：整個二叉樹的根結點未必是A結點，也可能是B結點）

根據之前的分析，要讓LL的情況恢復平衡，需要B結點右旋，旋轉的結果就是新的二叉樹，其中->

根結點從A結點變為B結點
A結點的左子樹從以B結點為根結點的樹變為BR，A結點的右子樹AR沒變
B結點的左子樹BL沒變，B結點的右子樹從BR變為以A結點為根結點的樹

各個結點的子樹情況	二叉樹未"右旋"時	二叉樹"右旋"后
整棵二叉樹的根結點即gf->lchild或gf->rchild	gf->lchild或gf->rchild的值為A結點即f	gf->lchild或gf->rchild的值為B結點即p
A結點的左子樹即f->lchild	f->lchild是以B結點為根結點的子樹即p	f->lchild是子樹BR
A結點的右子樹即f->rchild	f->rchild是子樹AR	f->rchild是子樹AR
B結點的左子樹即p->lchild	p->lchild是子樹BL	p->lchild是子樹BL
B結點的右子樹即p->rchild	p->rchild是子樹BR	p->rchild是以A結點為根結點的子樹即f

對于代碼的書寫只需要針對發生改變的子樹和結點即可，還需要注意其中的邏輯（代碼不唯一）：

步驟一：對于A結點，由于A結點只有左子樹f->lchild發生了改變即從以B結點為根結點的子樹p變為子樹BR，所以可以是f->lchild = p->rchild;

步驟二：對于B結點，由于B結點只有右子樹p->rchild發生了改變即從子樹BR變為以A結點為根結點的子樹f，所以可以是p->rchild = f;

步驟三：對于整棵二叉樹，只有根結點發生了改變即從A結點f變為B結點p，所以可以是gf->lchild = p或gf->rchild = p;，

這樣就可以實現"右旋"操作，同時可以保證這棵二叉樹依然保持二叉排序樹的特性。

3.RR：在A結點的右孩子的右子樹中插入新結點導致A結點不平衡->需要左旋

以上述圖片為例，

灰色方形的框表示結點的子樹，該子樹的高度用H表示，其中這些子樹都是平衡的
BL表示B結點的左子樹，BR表示B結點的右子樹，AL表示A結點的左子樹

（本例中假設在插入新結點之后以A結點為根結點的子樹是"最小不平衡子樹"，且AL、BL、BR這三個部分的高度最開始必須都是相同的，原理同"LL里的思考"）

上述圖片中最左邊的二叉樹中A結點的右子樹是以B結點為根結點的樹，其中BL的高度為H，BR的高度也為H，算上B結點，根據二叉樹的定義可知以B結點為根結點的樹的高度為H+1（加的1是B結點的高度），A結點的左子樹是AL，高度為H，

所以A結點的平衡因子=H-(H+1)=-1，所以A結點是平衡的；B結點的平衡因子=H-H=0，所以B結點是平衡的，

此時在A結點的右孩子即B結點的右子樹BR中插入一個新結點（上述圖片中間的二叉樹），會導致A結點不平衡，這是因為B結點的右子樹BR變高了，BR的高度變為了H+1，所以A結點的右子樹整體來看高度變為了H+2，而A結點的左子樹AL的高度仍保持為H，所以此時A結點的平衡因子=H-(H+2)=-2，導致A結點不平衡；B結點的平衡因子=H-(H+1)=-1，所以B結點是平衡的，

（注：假定以A結點為根結點的二叉樹就是最小不平衡子樹）

因此需要調整以A結點為根結點的二叉樹（即上述圖片中最中間的二叉樹）使其保持平衡，

如下圖：

如上圖，

要調整以A結點為根結點的二叉樹即"最小不平衡子樹"（即上述圖片中最中間的二叉樹）使其平衡，

調整的結果需要滿足：

恢復"最小不平衡子樹"的平衡
使得"最小不平衡子樹"在調整之后依然滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"

在本例中結點的大小關系為AL<A<BL<B<BR（注：以A結點為根結點的二叉樹是二叉排序樹，在A結點的右子樹中的每一個結點的值都大于結點A的值，比如BL>A，B>A），

使得以A結點為根結點的二叉樹即"最小不平衡子樹"恢復平衡的處理方法如下：

步驟一：讓B結點左旋->具體的做法就是讓B結點向左上旋轉代替A結點成為該二叉樹的根結點，B結點的左子樹就是以A結點為根結點的樹；

步驟二：處理子樹AL、BL、BR->

首先看子樹BR，BR之前是B結點的右子樹，BR的值大于B結點值(BR>B)，所以只能把BR連接在B結點的右子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹AL，AL之前是A結點的左子樹，有AL的值小于A結點的值(AL<A)，所以AL必須作為A結點的左子樹
最后看子樹BL，BL之前是B結點的左子樹，現在B結點的左子樹已經掛了A結點，那么BL就不能作為B結點的左子樹了，但是有BL的值大于A結點的值且小于B結點的值(B>BL>A)，所以可以把子樹BL當作A結點的右子樹(BL在B結點的左子樹中)

這樣就可以既保證二叉排序樹的特性，同時BR這個部分的高度是H+1即成功插入了新結點，

經過上述的調整之后(上述圖片最右邊的樹)B結點的左子樹的高度為H+1、右子樹BR的高度為H+1，即B結點的平衡因子=(H+1)-(H+1)=0，

A結點的左子樹AL的高度為H、右子樹BL的高度為H，即A結點的平衡因子=H-H=0，

可知以A結點為根結點的子樹和以B結點為根結點的子樹都保持了平衡，

這樣一來就可以讓"最小不平衡子樹"恢復平衡，同時又保持二叉排序樹的特性。

4.RR的代碼實現：

以上述圖片中的二叉排序樹為例，

f指針(father的縮寫)指向A結點即f指針表示A結點；A結點的左子樹為f->lchild；A結點的右子樹為f->rchild（注：f指針始終指向A結點，不會改變）
p指針指向B結點即p指針表示B結點；B結點的左子樹為p->lchild；B結點的右子樹為p->rchild（注：p指針始終指向B結點，不會改變）
gf指針(grandfather的縮寫)指向整個二叉樹的根結點的父結點；由于整個二叉樹的根結點可能是其父結點的左孩子，也可能是右孩子，所以整個二叉樹的根結點既可能是gf->lchild，也可能是gf->rchild，因此gf->lchild或gf->rchild就表示整個二叉樹的根結點（注：整個二叉樹的根結點未必是A結點，也可能是B結點）

根據之前的分析，要讓RR的情況恢復平衡，需要B結點左旋，旋轉的結果就是新的二叉樹，其中->

根結點從A結點變為B結點
A結點的左子樹AL沒變，A結點的右子樹從以B結點為根結點的樹變為BL
B結點的左子樹從BL變為以A結點為根結點的樹，B結點的右子樹BR沒變

各個結點的子樹情況	二叉樹未"右旋"時	二叉樹"右旋"后
整棵二叉樹的根結點即gf->lchild或gf->rchild	gf->lchild或gf->rchild的值為A結點即f	gf->lchild或gf->rchild的值為B結點即p
A結點的左子樹即f->lchild	f->lchild是子樹AL	f->lchild是子樹AL
A結點的右子樹即f->rchild	f->rchild是以B結點為根結點的子樹即p	f->rchild是子樹BL
B結點的左子樹即p->lchild	p->lchild是子樹BL	p->lchild是以A結點為根結點的子樹即f
B結點的右子樹即p->rchild	p->rchild是子樹BR	p->rchild是子樹BR

對于代碼的書寫只需要針對發生改變的子樹和結點即可，還需要注意其中的邏輯（代碼不唯一）：

步驟一：對于A結點，由于A結點只有右子樹f->rchild發生了改變即從以B結點為根結點的子樹p變為子樹BL，所以可以是f->rchild = p->lchild;

步驟二：對于B結點，由于B結點只有左子樹p->lchild發生了改變即從子樹BL變為以A結點為根結點的子樹f，所以可以是p->lchild = f;

步驟三：對于整棵二叉樹，只有根結點發生了改變即從A結點f變為B結點p，所以可以是gf->lchild = p或gf->rchild = p;，

這樣就可以實現"左旋"操作，同時可以保證這棵二叉樹依然保持二叉排序樹的特性。

四.調整"最小不平衡子樹"->LR和RL：（代碼類似LL和RR，自行推理即可）

1.LR：在A結點的左孩子的右子樹中插入新結點導致A結點不平衡

以上述圖片為例，

灰色方形的框表示結點的子樹，該子樹的高度用H表示，其中這些子樹都是平衡的
BL表示B結點的左子樹，BR表示B結點的右子樹，AR表示A結點的右子樹

（本例中假設在插入新結點之后以A結點為根結點的子樹是"最小不平衡子樹"，且AR、BL、BR這三個部分的高度最開始必須都是相同的，原理同"LL里的思考"）

上述圖片中最左邊的二叉樹中A結點的左子樹是以B結點為根結點的樹，其中BL的高度為H，BR的高度也為H，算上B結點，根據二叉樹的定義可知以B結點為根結點的樹的高度為H+1（加的1是B結點的高度），A結點的右子樹是AR，高度為H，

所以A結點的平衡因子=(H+1)-H=1，所以A結點是平衡的；B結點的平衡因子=H-H=0，所以B結點是平衡的，

此時在A結點的左孩子即B結點的右子樹BR(上述圖片打錯了)中插入一個新結點（上述圖片中間的二叉樹），會導致A結點不平衡，這是因為B結點的右子樹BR變高了，BR的高度變為了H+1，所以A結點的左子樹整體來看高度變為了H+2，而A結點的右子樹AR的高度仍保持為H，所以此時A結點的平衡因子=(H+2)-H=2，導致A結點不平衡；B結點的平衡因子=H-(H+1)=-1，所以B結點是平衡的，

（注：假定以A結點為根結點的二叉樹就是最小不平衡子樹）

因此需要調整以A結點為根結點的二叉樹使其保持平衡->為了方便探討，需要把B結點的右子樹BR展開，

如下圖：

如上圖，

現在把B結點的右子樹BR展開，

假設子樹BR是以C結點為根結點的二叉樹，C結點的左子樹為CL，C結點的右子樹為CR，

最開始在上述圖片最左邊的二叉樹中由于子樹BR的高度為H，所以子樹CL、CR的高度都為H-1（CL、CR的高度最開始必須是相同的，原理同"LL里的思考"）->其中A結點的平衡因子=(H+1)-H=1即A結點是平衡的；B結點的平衡因子=H-H=0即B結點是平衡的；C結點的平衡因子=(H-1)-(H-1)=0即C結點是平衡的；

現在在子樹BR中插入新結點之后（上述圖片最右邊的二叉樹），子樹BR的高度變為H+1，這里可以假設把新結點插在了C結點的右子樹CR，導致子樹CR的高度變為了H（新結點也可以插在了C結點的左子樹CL，導致子樹CL的高度變為了H，無論是哪種情況，最終的處理方法都是一樣的，這里先假定插入的新結點在子樹CR上）->其中A結點的平衡因子=(H+2)-H=2即A結點是不平衡的；B結點的平衡因子=H-(H+1)=-1即B結點是平衡的；C結點的平衡因子=(H-1)-H=-1即C結點是平衡的；

使得"最小不平衡子樹"即以A結點為根結點的子樹（上述圖片最右邊的二叉樹）恢復平衡的處理方法如下圖：

如上圖：

要讓"最小不平衡子樹"即以A結點為根結點的子樹（上述圖片最右邊的二叉樹）恢復平衡，

核心就是讓該"最小不平衡子樹"中的C結點先"左旋"，讓C結點頂替B結點的位置，再讓C結點"右旋"，讓C結點頂替A結點的位置，

其中結點的大小關系為BL<B<CL<C<CR<A<AR（注：以A結點為根結點的二叉樹是二叉排序樹，在A結點的左子樹中的每一個結點的值都小于結點A的值，比如CL<A，CR<A；以B結點為根結點的二叉樹也是二叉排序樹，在B結點的右子樹中的每一個結點的值都大于結點B的值，比如B<C，B<CL，B<CR），

具體操作如下圖：

如上圖，

要調整以A結點為根結點的二叉樹即"最小不平衡子樹"使其平衡，

調整的結果需要滿足：

恢復"最小不平衡子樹"的平衡
使得"最小不平衡子樹"在調整之后依然滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"

在本例中結點的大小關系為BL<B<CL<C<CR<A<AR，

使得以A結點為根結點的二叉樹即"最小不平衡子樹"恢復平衡的處理方法如下：

步驟一：讓C結點左旋->具體的做法就是讓C結點向左上旋轉代替B結點，C結點的左子樹就是以B結點為根結點的樹；

步驟二：處理子樹BL、CL、CR、AR->

首先看子樹BL，BL之前是B結點的左子樹，BL的值小于B結點值(BL<B)，所以只能把BL連接在B結點的左子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹CL，CL之前是C結點的左子樹，現在C結點的左子樹已經掛了B結點，那么CL就不能作為C結點的左子樹了，但是有CL的值大于B結點的值(B<CL)，所以可以把子樹CL當作B結點的右子樹
再看子樹CR，CR之前是C結點的右子樹，有CR的值大于C結點的值(C<CR)，所以CR繼續作為C結點的右子樹
最后看子樹AR，AR之前是A結點的右子樹，有AR的值大于A結點的值(A<AR)，所以AR繼續作為A結點的右子樹

此時得到了上述圖片中最中間的二叉樹->其中A結點的平衡因子=(H+2)-H=2即A結點是不平衡的；B結點的平衡因子=H-(H-1)=1即B結點是平衡的；C結點的平衡因子=(H+1)-H=1即C結點是平衡的，只有A結點不平衡，所以繼續調整使得以A結點為根結點的二叉樹保持平衡，

步驟三：(上述圖片中最中間的二叉樹)讓C結點右旋->具體的做法就是讓C結點向右上旋轉代替A結點，C結點的右子樹就是以A結點為根結點的樹；

步驟四：處理子樹BL、CL、CR、AR->

首先看子樹BL，BL之前是B結點的左子樹，BL的值小于B結點值(BL<B)，所以只能把BL連接在B結點的左子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹CL，CL之前是B結點的右子樹，有CL的值大于B結點的值(B<CL)，所以CL繼續作為B結點的右子樹
再看子樹CR，CR之前是C結點的右子樹，現在C結點的右子樹已經掛了A結點，那么CR就不能作為C結點的右子樹了，但是有CR的值小于A結點的值(CR<A)，所以可以把子樹CR當作A結點的左子樹
最后看子樹AR，AR之前是A結點的右子樹，有AR的值大于A結點的值(A<AR)，所以AR繼續作為A結點的右子樹

這樣就可以既保證二叉排序樹的特性，同時BR這個部分的高度是H+1即成功插入了新結點，

經過上述的調整之后(上述圖片最右邊的樹)B結點的左子樹BL的高度為H、右子樹CL的高度為H-1，即B結點的平衡因子=H-(H-1)=1，

A結點的左子樹CR的高度為H、右子樹AR的高度為H，即A結點的平衡因子=H-H=0，

C結點的左子樹的高度為H+1、右子樹的高度為H+1，即C結點的平衡因子=(H+1)-(H+1)=0，

可知以A結點為根結點的子樹、以B結點為根結點的子樹和以C結點為根結點的子樹都保持了平衡，

這樣一來就可以讓"最小不平衡子樹"恢復平衡，同時又保持二叉排序樹的特性。

注意：

如上圖，

本例假定插入的新結點在子樹CR上，

實際上也有可能是插入在子樹CL上，這種情況的處理方式同子樹CL，

也可以保證使所有的結點都恢復平衡。

2.RL：在A結點的右孩子的左子樹中插入新結點導致A結點不平衡

以上述圖片為例，

灰色方形的框表示結點的子樹，該子樹的高度用H表示，其中這些子樹都是平衡的
BL表示B結點的左子樹，BR表示B結點的右子樹，AL表示A結點的左子樹

所以A結點的平衡因子=H-(H+1)=-1，所以A結點是平衡的；B結點的平衡因子=H-H=0，所以B結點是平衡的，

此時在A結點的右孩子即B結點的左子樹BL中插入一個新結點（上述圖片中間的二叉樹），會導致A結點不平衡，這是因為B結點的左子樹BL變高了，BL的高度變為了H+1，所以A結點的右子樹整體來看高度變為了H+2，而A結點的左子樹AL的高度仍保持為H，所以此時A結點的平衡因子=H-(H+2)=-2，導致A結點不平衡；B結點的平衡因子=(H+1)-H=1，所以B結點是平衡的，

（注：假定以A結點為根結點的二叉樹就是最小不平衡子樹）

因此需要調整以A結點為根結點的二叉樹使其保持平衡->為了方便探討，需要把B結點的左子樹BL展開，

如下圖：

如上圖，

現在把B結點的左子樹BL展開，

假設子樹BL是以C結點為根結點的二叉樹，C結點的左子樹為CL，C結點的右子樹為CR，

最開始在上述圖片最左邊的二叉樹中由于子樹BL的高度為H，所以子樹CL、CR的高度都為H-1（CL、CR的高度最開始必須是相同的，原理同"LL里的思考"）->其中A結點的平衡因子=H-(H+1)=-1即A結點是平衡的；B結點的平衡因子=H-H=0即B結點是平衡的；C結點的平衡因子=(H-1)-(H-1)=0即C結點是平衡的；

現在在子樹BL中插入新結點之后（上述圖片最右邊的二叉樹），子樹BL的高度變為H+1，這里可以假設把新結點插在了C結點的左子樹CL，導致子樹CL的高度變為了H（新結點也可以插在了C結點的右子樹CR，導致子樹CR的高度變為了H，無論是哪種情況，最終的處理方法都是一樣的，這里先假定插入的新結點在子樹CL上）->其中A結點的平衡因子=H-(H+2)=-2即A結點是不平衡的；B結點的平衡因子=(H+1)-H=1即B結點是平衡的；C結點的平衡因子=H-(H-1)=1即C結點是平衡的；

使得"最小不平衡子樹"即以A結點為根結點的子樹（上述圖片最右邊的二叉樹）恢復平衡的處理方法如下圖：

如上圖：

要讓"最小不平衡子樹"即以A結點為根結點的子樹（上述圖片最右邊的二叉樹）恢復平衡，

核心就是讓該"最小不平衡子樹"中的C結點先"右旋"，讓C結點頂替B結點的位置，再讓C結點"左旋"，讓C結點頂替A結點的位置，

其中結點的大小關系為AL<A<CL<C<CR<B<BR（注：以A結點為根結點的二叉樹是二叉排序樹，在A結點的右子樹中的每一個結點的值都大于結點A的值，比如A<CL，A<C，A<B；以B結點為根結點的二叉樹也是二叉排序樹，在B結點的左子樹中的每一個結點的值都小于結點B的值，比如C<B，CL<B，CR<B），

具體操作如下圖：

如上圖，

要調整以A結點為根結點的二叉樹即"最小不平衡子樹"使其平衡，

調整的結果需要滿足：

恢復"最小不平衡子樹"的平衡
使得"最小不平衡子樹"在調整之后依然滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"

在本例中結點的大小關系為AL<A<CL<C<CR<B<BR，

使得以A結點為根結點的二叉樹即"最小不平衡子樹"恢復平衡的處理方法如下：

步驟一：讓C結點右旋->具體的做法就是讓C結點向右上旋轉代替B結點，C結點的右子樹就是以B結點為根結點的樹；

步驟二：處理子樹AL、CL、CR、BR->

首先看子樹AL，AL之前是A結點的左子樹，AL的值小于A結點值(AL<A)，所以只能把AL連接在A結點的左子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹CL，CL之前是C結點的左子樹，有CL的值小于C結點的值(CL<C)，所以CL繼續作為C結點的左子樹
再看子樹CR，CR之前是C結點的右子樹，現在C結點的右子樹已經掛了B結點，那么CR就不能作為C結點的右子樹了，但是有CR的值小于B結點的值(CR<B)，所以可以把子樹CR當作B結點的左子樹
最后看子樹BR，BR之前是B結點的右子樹，有BR的值大于B結點的值(B<BR)，所以BR繼續作為B結點的右子樹

此時得到了上述圖片中最中間的二叉樹->其中A結點的平衡因子=H-(H+2)=-2即A結點是不平衡的；B結點的平衡因子=(H-1)-H=-1即B結點是平衡的；C結點的平衡因子=H-(H+1)=-1即C結點是平衡的，只有A結點不平衡，所以繼續調整使得以A結點為根結點的二叉樹保持平衡，

步驟三：(上述圖片中最中間的二叉樹)讓C結點左旋->具體的做法就是讓C結點向左上旋轉代替A結點，C結點的左子樹就是以A結點為根結點的樹；

步驟四：處理子樹AL、CL、CR、BR->

首先看子樹AL，AL之前是A結點的左子樹，AL的值小于A結點值(BL<B)，所以只能把AL連接在A結點的左子樹，因為要保證"左子樹結點值<根結點值<右子樹結點值"
再看子樹CL，CL之前是C結點的左子樹，現在C結點的左子樹已經掛了A結點，那么CL就不能作為C結點的左子樹了，但是有CL的值大于A結點的值(CL>A)，所以可以把子樹CL當作A結點的右子樹
再看子樹CR，CR之前是B結點的左子樹，有CR的值小于B結點的值(CR<B)，所以CR繼續作為B結點的左子樹
最后看子樹BR，BR之前是B結點的右子樹，有BR的值大于B結點的值(B<BR)，所以BR繼續作為B結點的右子樹

這樣就可以既保證二叉排序樹的特性，同時BL這個部分的高度是H+1即成功插入了新結點，

經過上述的調整之后(上述圖片最右邊的樹)B結點的左子樹CR的高度為H-1、右子樹BR的高度為H，即B結點的平衡因子=(H-1)-H=-1，

A結點的左子樹AL的高度為H、右子樹CL的高度為H，即A結點的平衡因子=H-H=0，

C結點的左子樹的高度為H+1、右子樹的高度為H+1，即C結點的平衡因子=(H+1)-(H+1)=0，

可知以A結點為根結點的子樹、以B結點為根結點的子樹和以C結點為根結點的子樹都保持了平衡，

這樣一來就可以讓"最小不平衡子樹"恢復平衡，同時又保持二叉排序樹的特性。

注意：

如上圖，

本例假定插入的新結點在子樹CL上，

實際上也有可能是插入在子樹CR上，這種情況的處理方式同子樹CL，

也可以保證使所有的結點都恢復平衡。

五.LL、RR、LR和RL的總結：

只有左孩子才能"右旋"；只有右孩子才能"左旋"->每一次旋轉都會導致這個孩子變成爹，爹變成孩子

六.填坑：

以上述圖片中最左邊的二叉排序樹為例，

此時已經插入了關鍵字為67的結點，導致關鍵字為70的結點不平衡(平衡因子為2)，導致該結點不平衡的原因是在其左孩子的左子樹上插入了一個新結點67，也就是"LL"型，

這種情況應該讓不平衡結點即關鍵字為70的結點的左孩子進行"右旋"，也就是關鍵字為68的結點替代關鍵字為70的結點的位置，然后關鍵字為70的結點成為關鍵字為68的結點的右孩子，67結點連在68結點的左邊，

之前說過68的右子樹要成為70的左子樹，但原本68的右子樹是一個空樹NULL，把68的右子樹連接在70結點的左子樹后相當于結點70的左子樹為NULL，因此經過"右旋"操作之后得到的結果如上述圖片最右邊的二叉樹，

現在要填的坑是，剛開始說過只要把"最小不平衡子樹"恢復平衡之后其他所有的結點都會恢復平衡，現在來解釋一下為什么會這樣，

如下圖：

如上圖，

之前介紹了"LL"、"RR"、"LR"、"RL"四種情況，

對于這四類情況抽象的假設，

剛開始整棵二叉樹的高度為H+2，

插入新結點之后會導致不平衡，這棵"最小不平衡子樹"的高度為H+3，

但是經過旋轉一系列的處理之后二叉樹的整體高度又恢復了H+2，

如下圖：

如上圖：

所以這就能解釋為什么只需要調整"最小不平衡子樹"就能恢復整個二叉樹的平衡，

"最小不平衡子樹"變的不平衡是因為插入新結點后它的高度加1，但是經過調整之后"最小不平衡子樹"的高度又會恢復成原來的高度，

所以對于"最小不平衡子樹"的根結點的父結點來說，只要把該"最小不平衡子樹"的高度恢復原狀，

"最小不平衡子樹"的根結點的父結點的平衡因子也就會恢復原狀，同樣的再往上的祖先結點也都會跟著恢復原狀，

因此只要把"最小不平衡子樹"的高度恢復原狀，那么其他結點的平衡因子也都會依次恢復，

所以在這種插入操作中只需要調整"最小不平衡子樹"，"最小不平衡子樹"恢復平衡后，其他結點就都可以恢復平衡。

七.練習：

1.例一：

以上述圖片最左邊的二叉排序樹為例，

現在要插入關鍵字為90的結點，根據二叉排序樹的特性可知應該連接到關鍵字為70的結點的右子樹上，最終得到上述圖片中最右邊的二叉樹，

插入關鍵字為90的結點后，它的父結點即關鍵字為70的結點以及其祖先結點的平衡因子都可能受到影響，

所以可以從下到上依次檢查關鍵字為90的結點的父結點和祖先節點的平衡因子，

當檢查到關鍵字為66的結點后，發現是第一個不平衡的結點，平衡因子為-2，

因此以66結點為根結點的子樹就是"最小不平衡子樹"，接下來只需要調整該"最小不平衡子樹"使其平衡即可，

66結點不平衡的原因是在它的右孩子68結點的右子樹中插入了一個新結點90，也就是"RR"型，

如下圖：

如上圖：

處理方式應該讓上述圖片中最右邊的二叉樹的不平衡結點66的右孩子68結點"左旋"，替代66結點的位置，

如下圖：

如上圖，

上述圖片中最左邊的二叉樹的不平衡結點66的右孩子68結點"左旋"，"左旋"操作會導致68結點的左孩子67結點變成66結點的右孩子（詳情見本篇"RR"），最終得到上述圖片中最右邊的二叉樹，

最后一定要驗證得出的二叉樹是否滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"，如果不滿足說明處理有問題，

經過調整之后，這棵"最小不平衡子樹"就恢復了平衡，同時其他的結點的平衡因子也恢復了平衡。

2.例二：

以上述圖片最左邊的二叉排序樹為例，

現在要插入關鍵字為63的結點，根據二叉排序樹的特性可知應該連接到關鍵字為60的結點的右子樹上，最終得到上述圖片中最右邊的二叉樹，

插入關鍵字為63的結點后，它的父結點即關鍵字為60的結點以及其祖先結點的平衡因子都可能受到影響，

所以可以從下到上依次檢查關鍵字為63的結點的父結點和祖先節點的平衡因子，

當檢查到關鍵字為50的結點后，發現是第一個不平衡的結點，平衡因子為-2，

因此以50結點為根結點的子樹就是"最小不平衡子樹"，接下來只需要調整該"最小不平衡子樹"使其平衡即可，

50結點不平衡的原因是在它的右孩子68結點的左子樹中插入了一個新結點63，也就是"RL"型，

這種類型要做的處理就是把不平衡結點即50結點的右孩子68結點的左孩子66結點先"右旋"，再"左旋"，

如下圖：

如上圖：

處理方式是首先讓上述圖片中最左邊的二叉樹的結點66右旋替代結點68的位置，結點68成為結點66的右孩子，

結點66的右孩子67結點變為結點68的左子樹（詳情見本篇"RL"），

最終得到上述圖片中最右邊的二叉樹，

如下圖：

如上圖，

需要繼續"左旋"操作，讓上述圖片中最左邊的二叉樹的結點66進行"左旋"替代結點50的位置，左旋之后結點66的左子樹(以結點60為根結點的子樹)應該成為結點50的右子樹，結點50成為結點66的左孩子，最終得到上述圖片中最右邊的二叉樹，

這樣的話整棵樹恢復了平衡，同時依然保持了二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"。

最后一定要驗證得出的二叉樹是否滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"，如果不滿足說明處理有問題，

經過調整之后，這棵"最小不平衡子樹"就恢復了平衡，同時其他的結點的平衡因子也恢復了平衡。

3.例三：

以上述圖片最左邊的二叉排序樹為例，

現在要插入關鍵字為57的結點，根據二叉排序樹的特性可知應該連接到關鍵字為55的結點的右子樹上，最終得到上述圖片中最右邊的二叉樹，

插入關鍵字為57的結點后，它的父結點即關鍵字為55的結點以及其祖先結點的平衡因子都可能受到影響，

所以可以從下到上依次檢查關鍵字為57的結點的父結點和祖先節點的平衡因子，

當檢查到關鍵字為66的結點后，發現是第一個不平衡的結點，平衡因子為2，

因此以66結點為根結點的子樹就是"最小不平衡子樹"，接下來只需要調整該"最小不平衡子樹"使其平衡即可，

66結點不平衡的原因是在它的左孩子50結點的右子樹中插入了一個新結點57，也就是"LR"型，

這種類型要做的處理就是把不平衡結點即66結點的左孩子50結點的右孩子60結點先"左旋"，再"右旋"，

如下圖：

如上圖：

將上述圖片中最左邊的二叉樹中的60結點先"左旋"，再"右旋"，最終得到上述圖片中最右邊的二叉樹（詳情見本篇"LR"），

這樣的話整棵樹恢復了平衡，同時依然保持了二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"。

最后一定要驗證得出的二叉樹是否滿足二叉排序樹的特性即"左子樹結點值<根結點值<右子樹結點值"，如果不滿足說明處理有問題，

經過調整之后，這棵"最小不平衡子樹"就恢復了平衡，同時其他的結點的平衡因子也恢復了平衡。

八.查找效率分析：

如上圖，

在一棵二叉排序樹中進行查找操作，查找效率主要來自于該二叉排序樹的高度（詳情見"7.5.二叉排序樹(英文縮寫為BST，又名二叉查找樹)"），

假設當前二叉排序樹的高度為h，那么查找任何一個關鍵字最多需要對比h次（詳情見"7.5.二叉排序樹(英文縮寫為BST，又名二叉查找樹)"），

所以在二叉排序樹中進行查找操作的時間復雜度不會超過O(h)，也就意味著平均查找長度即ASL不會超過O(h)，

由此可知分析平衡二叉樹的查找效率，其實就是分析該平衡二叉樹的高度到底有多高，

基于平衡二叉樹的特性，

用N(h)表示深度為h的平衡二叉樹含有的最少的結點個數，

當h為0時該平衡二叉樹為空樹，那么該平衡二叉樹的結點個數N0為0，

當h為1時該平衡二叉樹只有1個根結點，那么該平衡二叉樹的結點個數N1為1，

當h為2時該平衡二叉樹中，它的結點最少有2個即根結點和其左孩子或者右孩子，那么該平衡二叉樹的結點個數N2為2，

再基于平衡二叉樹"樹上任一結點的左子樹和右子樹的高度只差不超過1"的遞歸特性可以得出N(h)=N(h-1)+N(h-2)+1，

即高度為h的平衡二叉樹的結點個數最少的情況應該是1個根結點，加其左子樹，該左子樹的高度為h-1，同時要保證左子樹的結點數最小，再加其右子樹，該右子樹的高度為h-2，并且也要保證右子樹的結點數最小，

所以可知N3為4，N4為7，N5為12，以此類推，

因此如果一棵平衡二叉樹的結點總數N為9，那么它的高度h最大為4->它的高度不可能為3，因為現在有9個結點，已經超出了N4；它的高度要到5的話，最少需要12個結點，

所以對于總共有9個結點的平衡二叉樹來說，在這棵二叉樹上查找一個關鍵字，最壞的情況也就需要對比4次關鍵字。

如果平衡二叉樹的結點總數為N，高度為h，基于N(h)=N(h-1)+N(h-2)+1這個公式可以證明平衡二叉樹的最大高度是O(log?N)的數量級（推導過程可以參考"5.4.二叉樹的性質"），

而平衡二叉樹的最大高度又反應了在最壞情況下查找操作的時間復雜度，因此最壞情況下平衡二叉樹的ASL或者查找操作的時間復雜度為O(log?N)->推導過程很復雜，如下圖：