背景
接著上面那個(gè)二叉搜索樹來講补履。有思考過二叉搜索樹最差的搜索時(shí)間復(fù)雜度嗎？最差的時(shí)候，二叉搜索樹插入的數(shù)據(jù)剛好是一條直線走哺，這樣時(shí)間復(fù)雜度就蛻變和鏈表沒什么區(qū)別（就是從O(logN)蛻變到O(n)級(jí)別）。因此AVL樹因此誕生了哲虾。
如下圖所示：
正文
AVL樹有什么概念呢丙躏？在二叉搜索樹之上，我們?yōu)榱吮ＷC整個(gè)樹都有左右節(jié)點(diǎn)束凑，盡量做到每個(gè)大小的節(jié)點(diǎn)都均勻分布彼哼，也就在二叉搜索上添加一個(gè)約束：
每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為1。
我們究竟怎么樣才能讓這個(gè)樹保證湘今，每個(gè)節(jié)點(diǎn)的左右樹高度差小于等于1呢敢朱？可以想象到的方案是，每一次加入一個(gè)新的節(jié)點(diǎn)摩瞎，或者刪除一個(gè)節(jié)點(diǎn)（也就是破壞平衡）拴签，通過不改變二叉搜索樹的基本原則下，對(duì)節(jié)點(diǎn)進(jìn)行調(diào)整旗们，最終達(dá)到每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為1的效果蚓哩。
下面是AVL樹算法給出的調(diào)整方案。
首先是兩個(gè)基礎(chǔ)旋轉(zhuǎn)方案上渴，左旋以及右旋：
左旋
從上圖可以看到岸梨，此時(shí)b的左右子樹高度明顯不平衡。整個(gè)樹往右邊長(zhǎng)了稠氮，導(dǎo)致了節(jié)點(diǎn)分布不均曹阔。所以我們需要人為的調(diào)整。
很淺顯的道理隔披，右邊多了赃份，就把右邊的部分修建下來，移動(dòng)到左邊去。就像修建樹木一樣抓韩。為了保證二叉搜索樹的結(jié)構(gòu)不被破壞纠永，我們需要A右邊的節(jié)點(diǎn)作為根移動(dòng)到A的位置，A比B小就移動(dòng)到左邊谒拴，這樣二叉樹又一次平衡起來了尝江。
這樣不就遺失掉一些節(jié)點(diǎn)嗎？所以我們需要去看看A占掉的節(jié)點(diǎn)位置英上，我們要移動(dòng)到A下面茂装，此時(shí)B的左節(jié)點(diǎn)還是比A大的，所以善延，C就移動(dòng)到了A的右側(cè)少态。
右旋
和上面相同的道理。此時(shí)左邊的樹更長(zhǎng)了易遣，為了樹的平衡彼妻，我們向右旋轉(zhuǎn)，這個(gè)樹豆茫，B成為了根侨歉，A就到了B的右側(cè)，B的右節(jié)點(diǎn)就到了A的左側(cè)揩魂。
小總結(jié)
記住幽邓，往那邊旋轉(zhuǎn)，哪邊的子樹不需要變動(dòng)火脉。而相反方向的節(jié)點(diǎn)牵舵，由于被原來的根代替了，遺留下來的子樹倦挂，所以就去到了原來根下面找合適的位置畸颅，左旋加到右邊，右旋加到左邊方援。
這樣總結(jié)下來還是看起來挺平衡的没炒。
但是也別太樂觀，光是這兩種旋轉(zhuǎn)還是不能處理一些長(zhǎng)得歪歪扭扭的樹犯戏，有時(shí)候光是一種旋轉(zhuǎn)是沒有辦法處理送火。可能需要兩種旋轉(zhuǎn)一起處理先匪，才能完成樹的平衡种吸。
比如說這種情況：
左右旋
當(dāng)出現(xiàn)原本應(yīng)該往左邊長(zhǎng)的樹，卻一直往右邊長(zhǎng)的樹胚鸯。我們嘗試著單次旋轉(zhuǎn)如上圖的第一步骨稿。無論是向左旋笨鸡，還是向右旋姜钳。你會(huì)發(fā)現(xiàn)都不平衡坦冠。比如說試試右旋，你會(huì)發(fā)現(xiàn)B右邊的節(jié)點(diǎn)已經(jīng)被C占有哥桥，A無法處理辙浑。
因此，在這種情況下拟糕，我們可以對(duì)著該節(jié)點(diǎn)的子樹進(jìn)行一次左旋判呕，來達(dá)到可以一次旋轉(zhuǎn)處理的情況。
右左旋
右左旋的思路同上送滞，因?yàn)樽鲆淮涡D(zhuǎn)侠草，我們無法平衡樹，所以先做一次旋轉(zhuǎn)達(dá)到能夠處理的情況犁嗅。如上圖所示边涕，樹本應(yīng)該向右邊生長(zhǎng)，而此時(shí)B節(jié)點(diǎn)右邊沒長(zhǎng)褂微，反而左邊一直長(zhǎng)功蜓。所以我們要處理的，就是把b右旋之后宠蚂，再把a(bǔ)左旋式撼，此時(shí)樹就平橫了。
AVL樹算法實(shí)現(xiàn)
關(guān)鍵的四個(gè)操作已經(jīng)明白了求厕，我們這一次也是實(shí)現(xiàn)增刪查改著隆。
我們一樣還是構(gòu)造出樹節(jié)點(diǎn)的基本類。
template <class K,class V>
class TreeNode{
public:
TreeNode *left = NULL;
TreeNode *right = NULL;
K key;
V value;
int height;
TreeNode(TreeNode* node){
this->left = node->left;
this->right = node->right;
this->key = node->key;
this->value = node->value;
this->height = node->height;
}
TreeNode(K key,V value):height(1){
this->left = NULL;
this->right = NULL;
this->key = key;
this->value = value;
}
};
你會(huì)發(fā)現(xiàn)比起二叉搜索樹呀癣，多了一個(gè)height屬性旅东，為的就是每一次添加之后，判斷高度是否最大不超過1十艾，超過則進(jìn)行旋轉(zhuǎn)處理抵代。
接下來寫一個(gè)，獲取子樹高度的方法忘嫉。
int getHeight(TreeNode *node){
return node ? node->height : 0;
}
解析來荤牍，我們來寫寫左旋和右旋的基礎(chǔ)方法：
左旋
//對(duì)著根節(jié)點(diǎn)左旋
TreeNode<K,V>* L_Rotation(TreeNode<K,V> *node){
//右節(jié)點(diǎn)挪動(dòng)到根部位置
TreeNode<K,V> *result_root = node->right;
//移動(dòng)到根的時(shí)候，此時(shí)之前的根庆冕，變成了左節(jié)點(diǎn)
//記住往哪里旋轉(zhuǎn)哪里不變康吵，變化的是相反方向的節(jié)點(diǎn)
//此時(shí)node 的 right不再是 變化后的根節(jié)點(diǎn)了，而是替換成了根后面的左節(jié)點(diǎn)
node->right = result_root->left;
//根節(jié)點(diǎn)變成右節(jié)點(diǎn)
result_root->left = node;
//處理完根節(jié)點(diǎn)之后访递，記住要處理一下高度
//這邊的高度是獲取子樹最大高度晦嵌，已經(jīng)更新當(dāng)前節(jié)點(diǎn)高度
node->height = max(getHeight(node->left)
,getHeight(node->right)) + 1;
result_root->height = max(getHeight(result_root->left),getHeight(result_root->right)) + 1;
return result_root;
}
右旋
//對(duì)著根節(jié)點(diǎn)右旋
TreeNode<K,V>* R_Roation(TreeNode<K,V> *node){
//左孩子移動(dòng)到根部
TreeNode<K,V> *result_root = node->left;
//此時(shí)原來左孩子的右側(cè)已經(jīng)是根了，原來的左孩子根部比此時(shí)的根小，則放到右側(cè)
node->left = result_root->right;
//原來的根節(jié)點(diǎn)變成了右孩子
result_root->right = node;
node->height = max(getHeight(node->left)
,getHeight(node->right)) + 1;
result_root->height = max(getHeight(result_root->left),getHeight(result_root->right)) + 1;
return result_root;
}
左右旋
根據(jù)左右旋的圖惭载，發(fā)現(xiàn)這個(gè)樹最好應(yīng)該往左邊生長(zhǎng)的旱函，但是卻往右邊長(zhǎng)，長(zhǎng)歪了描滔。所以要去找左節(jié)點(diǎn)進(jìn)行左旋之后棒妨，再對(duì)根節(jié)點(diǎn)右旋。
//先左旋含长，后右旋
TreeNode<K,V> *LR_Roation(TreeNode *node){
//本應(yīng)該這個(gè)樹是往左邊生長(zhǎng)的券腔，但是卻往右邊一直長(zhǎng)，所以先獲取左邊孩子
node->left = L_Rotation(node->left);
return R_Roation(node);
}
右左旋
TreeNode<K,V> *RL_Roation(TreeNode *node){
node->right = R_Roation(node->right);
return L_Rotation(node);
}
AVL 樹的插入
TreeNode *addNode(TreeNode *node,K key,V value){
if(!node){
count++;
return new TreeNode<K,V>(key,value);
}
if(key < node->key){
node->left = addNode(node->left,key,value);
} else if(key > node->key){
node->right = addNode(node->right,key,value);
} else{
node->value = value;
}
return node;
}
實(shí)際上AVL樹是早二叉搜索樹上發(fā)展而來的拘泞。所以把上文的插入節(jié)點(diǎn)的方法拷貝過來纷纫。在插入之后，我們需要做適當(dāng)?shù)恼{(diào)整陪腌。
根據(jù)上面的邏輯涛酗，我們繼續(xù)思考下去。那是結(jié)構(gòu)十分簡(jiǎn)單的AVL樹偷厦，但是當(dāng)我們擴(kuò)展到高度更高的樹的時(shí)候商叹，我們就要對(duì)每一層都要處理一次。換到代碼邏輯中就是在一層都添加一次高度判斷只泼，是否需要旋轉(zhuǎn)剖笙。
我們?cè)龠M(jìn)一步的思考下去，是不是每一次我們都要判斷是左旋還是右旋请唱，還是左右旋呢库糠？
實(shí)際上被济，根據(jù)我在上面講的。我們需要注意生長(zhǎng)方向，如果這棵樹是往左邊找節(jié)點(diǎn)添加的坠韩，說明樹的生長(zhǎng)方向是往左邊的雀哨。
也就是說埋凯，我們只需要判斷右旋還是左右旋即可锅减。因?yàn)樽筮叺墓?jié)點(diǎn)已經(jīng)足夠多了，不可能左旋甚亭，導(dǎo)致AVL樹更加歪贷币，而應(yīng)該右旋。再繼續(xù)深度思考下去亏狰，那假如從左邊找卻發(fā)現(xiàn)了右邊的樹更高役纹，那說明我們期待本應(yīng)該一直左長(zhǎng)的樹能夠一次解決，卻長(zhǎng)得更歪了暇唾，只能做一次左旋再右旋.
那么相同的道理能換算到右邊去促脉。
TreeNode<K,V>* addNode(TreeNode<K,V> *node,K key,V value){
if(!node){
count++;
return new TreeNode<K,V>(key,value);
}
if(key < node->key){
node->left = addNode(node->left,key,value);
if(getHeight(node->left) - getHeight(node->right) == 2){
if(getHeight(node->left->left) >= getHeight(node->left->right)){
//說明樹往左邊長(zhǎng)辰斋，能夠正常的單次旋轉(zhuǎn)解決
node = R_Roation(node);
} else if(getHeight(node->left->left) < getHeight(node->left->right)){
//否則是左邊的樹長(zhǎng)歪了，需要先左旋再右旋瘸味。
node = LR_Roation(node);
}
}
} else if(key > node->key){
node->right = addNode(node->right,key,value);
if(getHeight(node->right) - getHeight(node->left) == 2){
if(getHeight(node->right->right) > getHeight(node->right->left)){
//說明樹往右邊長(zhǎng)
node = L_Rotation(node);
} else if(getHeight(node->right->right) < getHeight(node->right->left)){
node = RL_Roation(node);
}
}
} else{
node->value = value;
}
node->height = max(getHeight(node->left),getHeight(node->right)) + 1;
return node;
}
void put(K key,V value){
root = addNode(root,key,value);
}
寫一個(gè)前序遍歷測(cè)試一下：
//前序遍歷,先根宫仗，后左，最后右
void levelTravel(void (*fun)(K, V)){
if(!root){
return;
}
TreeNode<K,V> *node = root;
queue<TreeNode<K,V>*> nodes;
nodes.push(root);
while (!nodes.empty()){
TreeNode<K,V> *p = nodes.front();
fun(p->key,p->value);
nodes.pop();
if(p->left){
nodes.push(p->left);
}
if(p->right){
nodes.push(p->right);
}
}
}
AVL<int,int> *avl = new AVL<int,int>();
avl->put(3,3);
avl->put(1,1);
avl->put(2,2);
avl->put(4,4);
avl->put(5,5);
avl->put(6,6);
avl->put(7,7);
avl->put(10,10);
avl->put(9,9);
avl->put(8,8);
avl->levelTravel(visit);
讓我們推導(dǎo)一邊流程硫戈，看看結(jié)果是否正確锰什。
先分批分析下硕，先看看從3開始一路加到5如何丁逝。
我們接著看看從6-10的過程
根據(jù)先序遍歷，打印順序是4梭姓，2霜幼，7，1誉尖，3罪既，6，9铡恕，5琢感，8，10
順序正確探熔，測(cè)試完畢驹针。
AVL樹的刪除
avl 樹的刪除比起插入，稍微有點(diǎn)復(fù)雜诀艰。但是扣緊定義柬甥，來實(shí)際上并不困難。
實(shí)際上我們要考慮的事情有一下幾點(diǎn)：
1.刪除葉子節(jié)點(diǎn)其垄，也就是沒有任何子節(jié)點(diǎn)苛蒲。
2.只有一個(gè)節(jié)點(diǎn)
3.有兩個(gè)節(jié)點(diǎn)的時(shí)候。
這個(gè)時(shí)候的思考方式和二叉搜索樹十分相似绿满。在刪除節(jié)點(diǎn)的時(shí)候臂外，只需要直接刪除，但是還是要注意平衡喇颁。刪除只有一個(gè)節(jié)點(diǎn)寄月，就沒有必要去找前驅(qū)后繼，畢竟此時(shí)樹的生長(zhǎng)方向只有一個(gè)无牵。在刪除兩個(gè)節(jié)點(diǎn)的時(shí)候則要考慮前驅(qū)后繼的問題漾肮，因?yàn)闃渫鶅蓚€(gè)方向生長(zhǎng)，想要保證二叉搜索樹的性質(zhì)茎毁，只能兩方面的考慮克懊。
最后記得忱辅，把節(jié)點(diǎn)調(diào)整回來。
TreeNode<K,V>* removeNode(TreeNode<K,V> *node,K key){
if(!node){
count--;
return NULL;
}
if(key < node->key){
node->left = removeNode(node->left,key);
if(getHeight(node->right) - getHeight(node->left) == 2){
if(getHeight(node->right->right) > getHeight(node->right->left)){
//說明樹往右邊長(zhǎng)
node = L_Rotation(node);
} else if(getHeight(node->right->right) < getHeight(node->right->left)){
node = RL_Roation(node);
}
}
} else if(key > node->key){
node->right = removeNode(node->right,key);
if(getHeight(node->left) - getHeight(node->right) == 2){
if(getHeight(node->left->left) >= getHeight(node->left->right)){
//說明樹往左邊長(zhǎng)谭溉，能夠正常的單次旋轉(zhuǎn)解決
node = R_Roation(node);
} else if(getHeight(node->left->left) < getHeight(node->left->right)){
//否則是左邊的樹長(zhǎng)歪了墙懂，需要先左旋再右旋。
node = LR_Roation(node);
}
}
} else{
//按照情況區(qū)分
//1.左右無節(jié)點(diǎn)
//2扮念。左右有節(jié)點(diǎn)
//3损搬。只有左或者右節(jié)點(diǎn)
count--;
if(!node->left&&!node->right){
delete(node);
return NULL;
} else if(node->left && node->right){
//左右都有節(jié)點(diǎn)
//需要特殊處理,找到是左邊高，還是右邊高
if(getHeight(node->left) > getHeight(node->right)){
//這種做法是為了盡可能的避免調(diào)整過多的旋轉(zhuǎn)柜与，
// 所以我們將會(huì)拿出多出那一塊的后繼或者前驅(qū)補(bǔ)充上去
//此時(shí)是左邊高巧勤，我們從左樹獲取最大值
TreeNode<K,V> *max = new TreeNode<K,V>(maxium(node->left));
//重新設(shè)置值
max->left = removeNode(node->left,max->key);
//原來那個(gè)還存在
max->right = node->right;
delete(node);
node = max;
} else{
//此時(shí)是右邊高，我們從右樹獲取最小值
TreeNode<K,V> *min = new TreeNode<K,V>(minium(node->right));
//重新設(shè)置值
min->right = removeNode(node->right,min->key);
//原來那個(gè)還存在
min->left = node->left;
delete(node);
node = min;
}
} else if(node->left){
TreeNode<K,V> *left = node->left;
delete(node);
return left;
} else{
TreeNode<K,V> *right = node->right;
delete(node);
return right;
}
}
return node;
}
void remove(K key){
root = removeNode(root,key);
}
此時(shí)弄匕，我們需要考慮的更多的是颅悉，我們實(shí)際上我們?cè)谕筮呥€是右邊尋找節(jié)點(diǎn)刪除的時(shí)候，必定會(huì)破壞平衡迁匠。當(dāng)我們刪除的左邊節(jié)點(diǎn)時(shí)候剩瓶，必定導(dǎo)致右邊多出一個(gè)高度，此時(shí)我們只需要考慮左旋和右左旋城丧。而不需要考慮右旋和左右旋延曙。同理?yè)Q到另一個(gè)方向去。
測(cè)試：
AVL<int,int> *avl = new AVL<int,int>();
avl->put(3,3);
avl->put(1,1);
avl->put(2,2);
avl->put(4,4);
avl->put(5,5);
avl->put(6,6);
avl->put(7,7);
avl->put(10,10);
avl->put(9,9);
avl->put(8,8);
avl->remove(8);
avl->remove(4);
avl->remove(6);
avl->remove(10);
avl->levelTravel(visit);
選擇幾個(gè)特殊的節(jié)點(diǎn)亡哄，測(cè)試結(jié)果：
再一次分解一下動(dòng)作看看枝缔。
而查和搜索二叉樹，沒有任何區(qū)別磺平。
至此魂仍，avl樹的增刪查改，已經(jīng)全部梳理一遍拣挪。
后話
接下來擦酌，就是紅黑樹了。avl樹屬于比較好理解的樹菠劝，并不復(fù)雜赊舶，只要理清楚思路就能盲敲出來。
