平衡二叉搜索樹是一種結(jié)構(gòu)平衡的二叉搜索樹雁社，它的每個(gè)結(jié)點(diǎn)的左右兩棵子樹的高度差都不超過一的二叉樹浴井。它可以在平均和最壞情況下都在的時(shí)間復(fù)雜度內(nèi)完成插入、刪除和查詢等操作霉撵。

正常的二叉搜索樹最好可以在的時(shí)間內(nèi)完成查詢等操作磺浙，但是如果二叉樹退化為單鏈表，那么其的搜索效率降低為徒坡。因此提出了平衡二叉搜索樹撕氧，來保持樹左右兩端深度的平衡。

定義

平衡二叉搜索樹又叫AVL樹喇完，簡(jiǎn)稱為平衡二叉樹伦泥，它需要滿足以下性質(zhì)：

1. 可以為空樹。
2. 如果不為空樹锦溪，則任意一個(gè)結(jié)點(diǎn)的左子樹和右子樹都是平衡二叉樹不脯，且高度之差的絕對(duì)值不超過1。

為了度量一棵二叉搜索樹是否為平衡二叉搜索樹引入了平衡因子刻诊，它是表示某結(jié)點(diǎn)左子樹和右子樹高度的差防楷，平衡二叉樹中不存在平衡因子絕對(duì)值大于1的結(jié)點(diǎn)。

失衡調(diào)整

了解平衡調(diào)整策略之前先引入一個(gè)最小失衡子樹的概念：在新插入的結(jié)點(diǎn)向上查找则涯，以第一個(gè)平衡因子的絕對(duì)值超過1的結(jié)點(diǎn)為根的子樹复局。平衡二叉樹的失衡調(diào)整主要通過旋轉(zhuǎn)最小失衡子樹實(shí)現(xiàn)的（旋轉(zhuǎn)的目的是為了調(diào)整左右子樹的高度，哪棵子樹高哪棵子樹向上旋轉(zhuǎn)）是整。旋轉(zhuǎn)常見的兩種方法為左旋和右旋肖揣。

左旋

平衡二叉搜索樹-01.png

如上圖所式，插入99結(jié)點(diǎn)之后不再滿足二叉平衡樹的性質(zhì)浮入，此時(shí)最小失衡子樹為以66結(jié)點(diǎn)為根的二叉樹龙优，對(duì)其進(jìn)行以下左旋操作：

1. 右孩子代替最小失衡子樹根所在的位置（77代替66的位置）
2. 右孩子的左子樹變?yōu)樵撟訕涓挠易訕洌?5的父結(jié)點(diǎn)改為66，作為右孩子）
3. 原來的根節(jié)點(diǎn)作為新子樹根的左孩子（66的父節(jié)點(diǎn)改為77事秀，作為左孩子）

平衡二叉搜索樹-02.png

右旋

平衡二叉搜索樹-03.png

如上圖所式彤断，插入43結(jié)點(diǎn)之后不再滿足二叉平衡樹的性質(zhì)，此時(shí)最小失衡子樹為以66結(jié)點(diǎn)為根的二叉樹易迹，對(duì)其進(jìn)行以下右旋操作：

1. 左孩子代替最小失衡子樹根所在的位置（60代替66的位置）
2. 左孩子的右子樹變?yōu)樵撟訕涓淖笞訕洌?3的父結(jié)點(diǎn)改為66S宰衙，作為左孩子）
3. 原來的根節(jié)點(diǎn)作為新子樹根的右孩子（66的父節(jié)點(diǎn)改為60，作為右孩子）

平衡二叉搜索樹-04.png

不同破壞平衡方式的調(diào)整方式

一般情況下睹欲，假設(shè)由于在二叉排序樹上插入結(jié)點(diǎn)而失去平衡的最小子樹根結(jié)點(diǎn)的指針為A（即A是離插入結(jié)點(diǎn)最近供炼，且平衡因子絕對(duì)值不超過1的祖先結(jié)點(diǎn)）一屋，則失去平衡后進(jìn)行調(diào)整的規(guī)律可以歸納為一下4種情況：

1. 在A的左子樹根節(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)而破壞平衡（LL）：使用單向右旋平衡方法。
2. 在A的右子樹根節(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)而破壞平衡（RR）：使用單向左旋平衡方法袋哼。
3. 在A的左子樹根節(jié)點(diǎn)的右子樹上插入結(jié)點(diǎn)而破壞平衡（LR）：使用先左旋后右旋的平衡處理方法冀墨。
4. 在A的右子樹根結(jié)點(diǎn)的左子樹上插入結(jié)點(diǎn)而破壞平衡（RL）：使用先右旋后左旋的平衡處理方法。

LL

該示例可以看此前失衡調(diào)整的右旋涛贯。

RR

該示例可以看此前失衡調(diào)整的左旋诽嘉。

LR

平衡二叉搜索樹-05.png

如上圖所示，插入65結(jié)點(diǎn)之后弟翘，不再是二叉平衡虫腋，此時(shí)再單純進(jìn)行右旋不能使樹重新平衡，因進(jìn)行以下操作：

1. 對(duì)失衡節(jié)點(diǎn)的左孩子進(jìn)行左旋操作（60為根進(jìn)行左旋）
2. 對(duì)失衡節(jié)點(diǎn)做右旋操作（66為根進(jìn)行右旋）

第一步：

平衡二叉搜索樹-06.png

第二步：

平衡二叉搜索樹-07.png

RL

平衡二叉搜索樹-08.png

如上圖所示稀余，插入76結(jié)點(diǎn)之后悦冀，不再是二叉平衡，此時(shí)再單純進(jìn)行左旋不能使樹重新平衡睛琳，因進(jìn)行以下操作：

1. 對(duì)失衡節(jié)點(diǎn)的右孩子進(jìn)行右旋操作雏门。（77為根進(jìn)行右旋）
2. 對(duì)失衡節(jié)點(diǎn)66做左旋操作（66為根進(jìn)行左旋）

第一步：

平衡二叉搜索樹-09.png

第二步：

平衡二叉搜索樹-10.png

總結(jié)

1. 在所有的不平衡情況中，都是按照先尋找最小不平衡樹掸掏，然后尋找所屬的不平衡類別，再根據(jù)4種類別進(jìn)行固定化程序的操作宙帝。
2. 在LR和RL中如果進(jìn)行第一次旋轉(zhuǎn)之后不論有沒有出現(xiàn)新的最小平衡樹丧凤，下一次調(diào)整的還是最初最小平衡樹的根節(jié)點(diǎn)。

刪除操作

這一部分我沒有找到很好的文獻(xiàn)步脓，希望有知道的同學(xué)們推薦一下愿待，下面是我對(duì)平衡二叉搜索樹刪除的理解。有錯(cuò)誤可以指出靴患，我修改一下仍侥。

上面講的都是平衡二叉搜索樹的插入。而平衡二叉搜索樹的刪除操作和二叉搜索樹的刪除一致鸳君，都有以下情況：

1. 如果結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)农渊，則直接刪除該結(jié)點(diǎn)，并從刪除結(jié)點(diǎn)的父結(jié)點(diǎn)開始檢查并調(diào)整或颊。
2. 如果結(jié)點(diǎn)只有左子樹或者右子樹中的一個(gè)砸紊，則直接將該子樹移到被刪除結(jié)點(diǎn)的位置，并從子樹頂結(jié)點(diǎn)開始向上檢查并調(diào)整囱挑。
3. 如果結(jié)點(diǎn)擁有兩個(gè)子樹醉顽，則用后繼或者先驅(qū)結(jié)點(diǎn)取代被刪除的結(jié)點(diǎn)，并從后繼或者先驅(qū)結(jié)點(diǎn)的父節(jié)點(diǎn)開始檢查并調(diào)整平挑。

參考文獻(xiàn)：

1. 什么是平衡二叉樹（AVL）
2. JAVA實(shí)現(xiàn)平衡二叉樹（AVL）——有源碼