AVL樹背景
在計算機科學中昧互，AVL樹是最先發(fā)明的自平衡二叉搜索樹（BBST）。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹坦辟。查找、插入和刪除在平均和最壞情況下都是O（log n）章办。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹锉走。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis滔吠，他們在 1962 年的論文 "An algorithm for the organization of information" 中發(fā)表了它。
BST -> BBST
BBST 核心技巧
1. 滿足適度平衡標準
2. 重平衡操作的技巧與算法
以 AVL樹 為例挠日，如何實現(xiàn)上述兩條核心
AVL 樹定義 ：
1. 首先滿足 BST 性質(zhì)
2. 或者為空樹疮绷，或者滿足以下性質(zhì)
- 任意節(jié)點的左右子樹高度差的絕對值不大于1
- 其左右子樹又都滿足 AVL樹
為此，引入 平衡因子 balFactor() ： 左子樹的高度減去右子樹的高度
- balFactor(V) = height( LC(V) ) - height( RC(V) ). 即V的左子樹高度-右子樹高度
則 AVL 滿足 ： -1<= balFactor(V) <=1 (取值只有-1 嚣潜， 0 冬骚，1)
注：AVL滿足適度平衡標準，有 height(AVL) = O( log n)
AVL相關(guān)接口
BinTree 中定義的 節(jié)點高度
#define NodeHeight(p) ((p) ? p->height : -1) //節(jié)點高度懂算，約定空樹的節(jié)點高度約定為 －1
AVL 接口
1. 理想平衡,左右子樹高度相等
#define Balanced(x) \
(NodeHeight(x->lchild) == NodeHeight(x->rchild))
2. 平衡因子
#define BalFator(x) \
(NodeHeight(x->lchild) - NodeHeight(x->rchild)
3. AVL 平衡條件 BalFactor(x)在 [-1,1] 之間
#define AVLBalanced(x) \
( (-2 < BalFactor(x) ) && ( BalFactor(x) < 2 )
4. AVL 查找 Search() ... 可直接沿用 BST 的接口 <詳見BST>
5. 需要重寫的只有引起 AVL 結(jié)構(gòu)變化的動態(tài)操作
5.1 插入操作
BinNodePosi insert(const T &);
5.2 刪除操作
bool remove(const T &);
下面主要介紹 AVL 樹的插入和刪除操作
失衡與重平衡
AVL 插入刪除操作
[注] insert操作 相比 remove操作 的重平衡簡單一點
1. AVL 插入節(jié)點操作
一個重要的結(jié)論 ： AVL樹 插入節(jié)點x只冻，同時可有
多個失衡節(jié)點，從節(jié)點x 向上追溯其祖先计技，找到第一個失衡點(也稱為最低失衡點)喜德，對最低失衡點進行"對應"的復衡操作(等價變換)，子樹的高度必然恢復垮媒，更高祖先也必復衡舍悯，全樹也就恢復平衡。[注]
最低失衡點概念總結(jié)
首先引入最小不平衡子樹： 插入節(jié)點導致失衡后睡雇，距離插入節(jié)點最近的萌衬，且平衡因子的絕對值大于 1 的節(jié)點為根的子樹。
這個節(jié)點就稱之為最低失衡點
對最小不平衡子樹進行復衡操作它抱，使子樹恢復平衡秕豫，全樹也會進而平衡。
- 上圖 insert(M) 操作观蓄，N 節(jié)點為最低失衡點混移。（N，K侮穿，M）為最小不平衡子樹
1.1. 在平衡的二叉排序樹(AVL)中插入一個節(jié)點歌径，當出現(xiàn)不平衡時，根據(jù)不平衡情況可分為四種不平衡類型 撮珠，這四種類型又可通過兩類操作"單旋沮脖，雙旋"來實現(xiàn)復衡
假設(shè)已知 最低失衡點 為A，根據(jù)新插入節(jié)點與A的位置關(guān)系來命名不平衡類型
- LL型：新插入節(jié)點在A的左孩子(L)的左子樹(L)中;
- LR型：新插入結(jié)點在A的左孩子(L)的右子樹(R)中;
- RL型：新插入結(jié)點在A的右孩子(R)的左子樹(L)中;
- RR型：新插入結(jié)點在A的右孩子(R)的右子樹(R)中;
圖解這四種類型芯急，以及其復衡操作
LL型 ： 右旋最低失衡點A（Zig(A)）
LL型
RR型 ：左旋最低失衡點A（Zag(A)）
RR型
LR型 ：
LR型
RL型 ：
RL型
下面通過更詳細的"單旋，雙旋操作步驟"來展示實現(xiàn)4類失衡情況復衡的過程
單旋 ：
- 對于 LL型 ： 只需對
最低失衡點A進行Zig(A)操作 - 對于 RR型 ：只需對
最低失衡點A進行Zag(A)操作
本質(zhì)上是一次等價變換的實現(xiàn)過程
-
以RR型為例驶俊，Zag(A)的等價變換過程
Zig - 本質(zhì)上是等價交換的過程娶耍，將
三個節(jié)點及其子樹按中序次序重構(gòu)即可
[注] 理解上，采用上面的"RR型"圖示展示的"2個節(jié)點+3棵子樹"來重新構(gòu)建即可饼酿，但是下面雙旋要以3+4結(jié)構(gòu)來實現(xiàn)重構(gòu)榕酒，所以單旋'委屈一下'適應雙旋胚膊，以便后續(xù)重構(gòu)算法的統(tǒng)一實現(xiàn)，而不是單旋寫一個重構(gòu)想鹰，雙旋也實現(xiàn)一個重構(gòu)紊婉。
雙旋 ：
- 對于 LR型 ： zag-zig
- 對于 RL型 ： zig-zag
與單旋類似，本質(zhì)上也是等價變換的過程
-
以 RL型為例辑舷，進行 zig-zag 操作的過程
Zig-Zag - 上圖中
失衡前的樹(1)到復衡后的樹(3)喻犁，本質(zhì)上就是等價交換的過程：即
A，B何缓，C三個節(jié)點與其對應的子樹肢础，按中序次序重新構(gòu)建，可恢復平衡
將上述的單旋碌廓，雙旋的操作過程理解清楚传轰，本質(zhì)上是等價交換的過程，下面的代碼實現(xiàn)也是基于這個思想谷婆，理解了這個過程慨蛙，也就理解了下述復衡算法實現(xiàn)的過程 。
重點＜涂妗９傻！
插入操作代碼實現(xiàn):
/*************************************/
#define FromParentTo(x) ( IsRoot(x) ? _root : ( IsLChild(x)? x.parent->lchild : x.parent->rchild) )
BinNodePosi insert(const T & e)
{
BinNodePosi &x = search(e); //查找插入點
if (x)
{
return x; //若目標已經(jīng)存在廷区，不執(zhí)行插入操作唯灵，直接返回
}
x = new BinNode(e, _hot); //找到待插入點，以_hot為父親隙轻，創(chuàng)建 x 埠帕，并插入
_size ++;
BinNodePosi xx = x;
//以下，從 x 的 父親出發(fā)玖绿，逐層向上敛瓷，依次檢查各代祖先，找到最低失衡點
for (BinNodePosi g = x->parent; g; g = g->parent)
{
if (!AvlBalanced(*g)) // 一旦發(fā)現(xiàn)g失衡斑匪，則找到最低失衡點呐籽，通過調(diào)整可恢復全樹平衡
{
//具體的重平衡實現(xiàn)函數(shù)
FromParentTo(*g) ＝ rotateAt( tallerChild(g) ); //旋轉(zhuǎn)重平衡操作
break;
}
else
{
//否則，只需要更新其高度(平衡度雖然不變蚀瘸，高度卻有可能改變)
updateHeight(g); //是只要更新該節(jié)點高度狡蝶，還是包括其祖先？贮勃？再整理一下
}
}
return x; //返回新節(jié)點贪惹，只需要一次調(diào)整！＜偶巍Ｗ嗨病枫绅；
}
2. AVL刪除節(jié)點操作
當出現(xiàn)不平衡狀態(tài)需要重平衡時，同樣通過"單旋"和"雙旋"兩類操作實現(xiàn)
- 單旋 ： LL型 和 RR型
- 同時至多一個失衡節(jié)點g硼端，首個可能的就是刪除節(jié)點 x 的父親節(jié)點 _hot
- g經(jīng)過單旋調(diào)整后恢復平衡并淋，子樹高度
未必復原，更高祖先仍可能失衡- 因有
失衡傳播現(xiàn)象珍昨，可能需要做 O(log n)次調(diào)整
-
雙旋 ： zig-zag 和 zag-zig
以 zag-zig 為例：
- 同時至多一個失衡節(jié)點g县耽，首個可能就是刪除節(jié)點x的父親_hot
- Zag(p)
Zig(g)- 因有
失衡傳播現(xiàn)象，可能需要做 O(log n )次調(diào)整
刪除操作代碼實現(xiàn):
/*************************************/
bool remove(const T &e)
{
BinNodePosi & x = search(e);
if ( !x )
{
return false; //待刪節(jié)點不存在
}
removeAt(x, _hot); //按常規(guī)的BST規(guī)模刪除之后曼尊，_hot及其祖先都有可能失衡
_size --;
//以下是刪除后的重平衡操作：從_hot出發(fā)逐層向上酬诀，依次檢查其祖先g
for (BinNodePosi g = _hot; g; g = g->parent)
{
if ( !AVLBalanced(*g) ) //一旦找到失衡點，則通過調(diào)整恢復平衡
{
g = FromParentTo(*g) = rotateAt( tallerChild( tallerChild(g) )); //旋轉(zhuǎn)重平衡操作
}
upDateHeight(g); //并更新其高度
} // 可能還需做多次調(diào)整Ｂ嫫病Ｂ饔！無論是否做過調(diào)整神郊，全樹高度均可能下降
return true;
}
上面AVL插入和刪除節(jié)點操作肴裙，重平衡講的很熱鬧
那么重平衡算法rotateAt()函數(shù)(也就是旋轉(zhuǎn)操作)到底是怎么實現(xiàn)的呢？
我們現(xiàn)在知道所謂的旋轉(zhuǎn)操作rotateAt()無外乎zig, zag, zig-zag, zag-zig四類
那么如何能夠高效的實現(xiàn)上述四類旋轉(zhuǎn)呢涌乳？
通過一些分析蜻懦，不難發(fā)現(xiàn)，所謂旋轉(zhuǎn)最后實現(xiàn)的復衡結(jié)構(gòu)夕晓，實際上是滿足中序次序的重新構(gòu)建宛乃，將理解上的旋轉(zhuǎn)操作轉(zhuǎn)換成邏輯上的構(gòu)建操作，復衡算法的實現(xiàn)也就很容易實現(xiàn)
下面著重講解蒸辆！
寫在前面
/* 刪除節(jié)點操作后的調(diào)整動作 */
/* 1. <3+4重構(gòu)> */
BinNodePosi connect34(BinNodePosi, BinNodePosi, BinNodePosi,
BinNodePosi, BinNodePosi, BinNodePosi, BinNodePosi);
/*2. <旋轉(zhuǎn)操作> */
BinNodePosi rotateAt(BinNodePosi);
"3＋4" 重構(gòu)算法
前面提及的 zig 征炼，zag 操作（單旋式，雙旋式）躬贡，主要是幫助對算法操作過程形成整體了解谆奥，在真正的實現(xiàn)時，我們不必機械地如此理解拂玻，通過上面的圖示酸些，也很容易看出復衡的過程，也就是 3個節(jié)點 + 4棵子樹的重新組合構(gòu)建的過程
AVL 重平衡過程：并非在乎平衡過程的技巧檐蚜，更在于高效率實現(xiàn)重平衡魄懂，引入高效重平衡算法"3＋4" 重構(gòu)算法
"3＋4" 重構(gòu)算法
- 設(shè) g 為最低失衡節(jié)點，考察祖孫三代 g ~ p ~ v
以中序遍歷次序（大邪旧酢）逢渔，將其重命名為 ： a < b < c （g，p乡括，v根據(jù)中序次序?qū)μ柸胱?br> 比如 LL 型 ： {v肃廓，p，g} 對應 {a诲泌，b盲赊，c}
比如 LR 型： {p，v敷扫，g} 對應 {a哀蘑，b，c}
此為 '3' , 表 3 個節(jié)點 - {g葵第，p绘迁，v}總共擁有互不相交的四顆（可能為空）的子樹，
按中序遍歷次序卒密，將其重命名為 T0 < T1 < T2 < T3
此為 '4' , 表 4 棵子樹 - 重構(gòu) :
- a 的左子樹為 T0缀台，T0的父親為a
a 的右子樹為 T1，T1的父親為a - c 的左子樹為 T2哮奇，T2的父親為c
c 的右子樹為 T3膛腐，T3的父親為c - b 的左孩子為 a，a 的父親為 b
b 的右孩子為 c鼎俘，c 的父親為 b
- a 的左子樹為 T0缀台，T0的父親為a
重構(gòu)
"3＋4" 重構(gòu)算法代碼實現(xiàn)：
BinNodePosi connect(BinNodePosi a, BinNodePosi b, BinNodePosi c,
BinNodePosi T0, BinNodePosi T1, BinNodePosi T3, BinNodePosi T4)
{
//重構(gòu)
a->lChild = T0;
if (T0)
{
T0 -> parent = a;
}
a->rchild = T1;
if (T1)
{
T1 -> parent = a;
}
updateHeight(a);
/**********************************************/
c->lChild = T2;
if (T2)
{
T2 -> parent = c;
}
c->rChild = T3;
if (T3)
{
T3 -> parent = c;
}
updateHeight(c);
/**********************************************/
b->lChild = a;
a->parent = b;
b->rChild = c;
c->parent = b;
updateHeight(b);
return b; //該子樹新的根節(jié)點
}
統(tǒng)一調(diào)整 ： 實現(xiàn)全樹的復衡 rotateAt() 旋轉(zhuǎn)操作
BinNodePosi rotateAt(BinNodePosi v)
{
BinNodePosi p = v->parent; //父親
BinNodePosi g = p->parent; //祖父
if ( IsLChild(*p) ) // L
{
if (IsLChild(*v)) // L-L型
{
p-parent = g->parent; //向上聯(lián)接
// 將 v, p, g 節(jié)點及其子樹按中序排一下哲身，作為入?yún)? return connect34(v, p, g, v->lchild, v->rchild, p->rchild, g->rchild);
}
else // L-R型
{
v->parent = g->parent; //向上聯(lián)接
return connect34(p, v, g, p->lchild, v->rchild, v->rchild, g->rchild);
}
}
else
{ // zag-zig , zag-zag
}
}
以 LL 型 和 LR 型為例，
LL型"3+4重構(gòu)"
LR型"3+4重構(gòu)"
[ 注 ] ：
3+4重構(gòu)的等價變換算法是為了統(tǒng)一解決單旋和雙旋對應的等價變換的Ｃ撤ァ？碧臁！誠然單旋LL型或RR型用2+3重構(gòu)也可以實現(xiàn)等價變換捉邢，但是雙旋的話卻不能以2+3實現(xiàn)脯丝，必須多引入一個節(jié)點，只能采用3+4歌逢，為統(tǒng)一實現(xiàn)單旋&雙旋巾钉，采用3+4，對于單旋無影響秘案。
綜合評價
- 優(yōu)點 ： 無論
search(),insert().remove()砰苍，最壞情況下的復雜度均為O(log n),O(n)的存儲空間 - 缺點 ： 借助
高度或平衡因子，為此需改造元素結(jié)構(gòu)阱高，或額外封裝
實測復雜度與理論值尚有差距
插入/刪除后的旋轉(zhuǎn)赚导，成本大
刪除操作重平衡，最多需要Ω(log n) 次
如果需要頻繁插入和刪除操作赤惊，未免得不償失
單次動態(tài)調(diào)整后吼旧，全樹的拓撲結(jié)構(gòu)的變化量可能高達Ω(log n)
`
