前言

學(xué)習(xí)了普通二叉樹，發(fā)現(xiàn)普通二叉樹作用不大，于是我們學(xué)習(xí)了搜索二叉樹，給二叉樹新增了搜索、排序、去重等特性，
但是，在極端情況下搜索二叉樹會退化成單邊樹，搜索的時間復(fù)雜度達(dá)到了O(N)，這是十分不利的，
所以，牛人們又提出了新的數(shù)據(jù)結(jié)構(gòu)：AVL樹（平衡搜索二叉樹），給搜索二叉樹新增了平衡的特性，控制左右子樹的高度，是搜索二叉樹處于平衡的狀態(tài)，避免出現(xiàn)極端情況。

AVL樹的發(fā)明者是兩位俄羅斯數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis，為了幾年他們在1962年提出該數(shù)據(jù)結(jié)構(gòu)，就命名為AVL樹。

---

AVL樹的特性

AVL樹要求任意節(jié)點(diǎn)的左右子樹的高度差的絕對值不超過1.
為什么擁有該特性AVL樹就可以保持平衡呢？這里需要數(shù)學(xué)證明，就不解釋了，理解原理后，就很容易理解。

一棵AVL樹是具有以下性質(zhì)的二叉搜索樹：

1. 它的左右子樹都是AVL樹
2. 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)

注意：在這里，我們引入一個變量，平衡因子（balance factor），用來記錄左右子樹的高度差，
這里我們記錄右子樹的高度減左子樹的高度。
當(dāng)然，也可以有其他的思路來替代平衡因子。

---

AVL樹節(jié)點(diǎn)的定義（以KV型為例）

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K,V>* _left = nullptr;//左子節(jié)點(diǎn)AVLTreeNode<K, V>* _right = nullptr;//右子節(jié)點(diǎn)AVLTreeNode<K, V>* _parent = nullptr;//父親節(jié)點(diǎn)pair<K, V> _kv;//數(shù)據(jù)int _bf = 0;//平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv){}
};

注意：AVL樹使用三叉鏈實(shí)現(xiàn)，多了一個parent指針，用來記錄父親節(jié)點(diǎn)，方便使用。

---

AVL樹的插入（核心）

AVL樹是在搜索二叉樹上面進(jìn)行升級，所以查找的方法和搜索二叉樹類似，大了就向右子樹走，小了就往左子樹走。

因?yàn)檫@里多了parent指針和bf，在插入之后都需要進(jìn)行維護(hù)。（天下沒有白吃的午餐，使用的時候方便，維護(hù)起來就麻煩了QAQ）

parent指針處理起來很簡單，我們這里主要講bf如何控制。

bf有三種取值 0 ， - 1 ， 1
當(dāng)我們在節(jié)點(diǎn)的右側(cè)插入的時候，節(jié)點(diǎn)的bf++，在節(jié)點(diǎn)的左側(cè)插入的時候，節(jié)點(diǎn)的bf–。

在右邊插入，右子樹的高度增加，bf++，在左邊插入的時候，左子樹的高度增加，bf–

這是毫無疑問的，以下都基于此。

OK，更新完當(dāng)前節(jié)點(diǎn)之后，bf就維護(hù)好了嗎？
哪有這么簡單QAQ

在插入后cur的bf更新為1，僅僅如此嗎？
看這張圖，parent的bf也要從1變成2了。

所以，在更新完cur節(jié)點(diǎn)的bf后，還需要根據(jù)情況確定是否要繼續(xù)向上更新

具體是否要更新，主要是看子樹的高度有沒有發(fā)生變化

有哪些情況呢？

1. cur插入后更新為0
   說明原來是1 或者 -1，在較短的那一條邊上新增了新節(jié)點(diǎn)，將cur節(jié)點(diǎn)變平衡了，
   這樣的話，那高度就沒有增加，不會影響到子樹的高度，就不需要向上更新bf了。
2. cur插入后更新為 1，-1
   說明原來是0，原來是平衡的，插入新節(jié)點(diǎn)后破壞了平衡，子樹高度發(fā)生了變化，
   所以需要向上更新bf。
3. cur插入后更新為 2，-2
   當(dāng)更新為2，-2后，發(fā)現(xiàn)違反了AVL樹的規(guī)則，不再是一顆AVL樹，我們就需要進(jìn)
   行特殊操作來維護(hù)AVL樹的性質(zhì)了。（這里，我們采用旋轉(zhuǎn)）

---

AVL樹的旋轉(zhuǎn)（最難的部分）

AVL樹的旋轉(zhuǎn)是AVL樹這個數(shù)據(jù)結(jié)構(gòu)的亮點(diǎn)，掌握了這一點(diǎn)之后，才會理解這種數(shù)據(jù)結(jié)構(gòu)有多么精妙。

從深層上看，AVL樹的旋轉(zhuǎn)分為四種情況，我們畫圖來分析。（由于實(shí)際情況太多太多，我們這里畫抽象圖）

左單旋

這里h >= 0
我們在最右邊插入一個節(jié)點(diǎn)，使AVL樹的右側(cè)完全傾斜，那么我們就需要向左側(cè)旋轉(zhuǎn)了。
如何向左旋轉(zhuǎn)呢？

我們將三個需要用到的節(jié)點(diǎn)命名一下，分別為parent，subR，以及subRL
根據(jù)搜索二叉樹的性質(zhì)，我們知道subRL > parent ，但是小于subR，所以就可以進(jìn)行左單旋而不會破壞搜索的性質(zhì)

左單旋就是
先將subRL插入到parent的右邊
接著將parent插入到subR的左邊

成功旋轉(zhuǎn)之后圖形變成下面的樣子

這樣左右子樹的高度就一樣了，重新將AVL樹調(diào)整平衡了
這里還有非常多的代碼細(xì)節(jié)，例如空指針，parent指針的維護(hù)等等需要處理，這里大家可以先嘗試根據(jù)思路寫出代碼，再跟后面的代碼進(jìn)行比較，看看是否寫對了。

這里只簡單講一下平衡因子的維護(hù)。
可以看到，在左單旋只會影響parent和subR兩個節(jié)點(diǎn)的bf，且旋轉(zhuǎn)后皆為0，故不用向上繼續(xù)調(diào)整。

---

右單旋

右單旋和左單旋類似，是對稱的，這里只簡單畫出抽象圖，相信讀者能夠自己理解。

右單旋就是處理左邊完全傾斜的情況，向右邊旋轉(zhuǎn)，進(jìn)而調(diào)整平衡。
代碼依舊在文末尾給出。

---

右左雙旋

顧名思義，先右單旋后左單旋構(gòu)成右左雙旋。
相信聰明的小伙伴，在看到左單旋和右單旋的時候，就會發(fā)現(xiàn)這兩種情況都是插入在最右邊和最左邊造成完全傾斜。
而插入在右子樹的左邊和左子樹的右邊都沒有列舉出來。

這里右左雙旋就是應(yīng)對插入在右子樹的左邊這種情況的，顯然，左右雙旋就是應(yīng)對插入在左子樹的右邊那種情況的，這里講右左雙旋，左右雙旋留給大家自己思考。

左單旋和右單旋都不適合這種情況，根本原因在于，這種情況并不是完全傾斜，很簡單嘛，
你不是完全傾斜，我強(qiáng)行讓你變成完全傾斜，不就可以使用左單旋或者右單旋了嘛。

對于這種情況，我們可以看到是subRL太高了，導(dǎo)致的不平衡，我們將subRL旋轉(zhuǎn)到subR的位置豈不是可以造成完全傾斜了嗎？

這右單旋不就來了嘛，使用右單旋就將subRL的右插入到subR的左，再將subR插入到subRL的右即可。

右單旋完了之后，就是下面的圖形

映入眼簾的就是右邊太高了，出現(xiàn)了完全傾斜，直接左單旋調(diào)整平衡即可。

這里同樣有很多代碼細(xì)節(jié)，要維護(hù)好parent和bf，以及處理好空指針的特殊情況。

這里還是只簡單講一下bf的維護(hù)
我們以終為始，只看旋轉(zhuǎn)前和旋轉(zhuǎn)后的兩幅圖。

我們可以看到只有三個節(jié)點(diǎn)60 30 90的bf發(fā)生了變化。
也就是只有parent，subR，subRL三個節(jié)點(diǎn)的bf發(fā)生了變化。
這里最后subRL和subR的bf 變成了0，parent的bf變成了-1。
但是，一定是這樣嗎？
這中情況是在c子樹上插入新節(jié)點(diǎn)，如果在b上插入新節(jié)點(diǎn)。
a和b的高度都是h，parent的bf就是0，c的高度是h-1，d的高度是h，subR的bf就是1

問題就在于是在subRL的左子樹插入還是右子樹插入新節(jié)點(diǎn)。
如何分辨?
很簡單，去觀察subRL的旋轉(zhuǎn)前的bf
如果是1，就是在右子樹插入，如果是-1，就是在左子樹插入

---

左右雙旋

大體和右左雙旋類似，所以這里簡單畫個抽象圖，相信讀者能夠自行理解。

這里就是新節(jié)點(diǎn)插入在了左子樹的右邊，導(dǎo)致不平衡，先左單旋調(diào)整成完全傾斜，在右單旋調(diào)整至平衡。

---

代碼

#include <assert.h>
#include <iostream>using namespace std;namespace Avltree//命名空間名不能和類名相同，不然會發(fā)生命名沖突
{template<class K, class V>struct AVLTreeNode{AVLTreeNode<K,V>* _left = nullptr;AVLTreeNode<K, V>* _right = nullptr;AVLTreeNode<K, V>* _parent = nullptr;pair<K, V> _kv;int _bf = 0;//平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv){}};template<class K,class V>class AVLTree{typedef AVLTreeNode<K, V> Node;private:Node* _root = nullptr;//開始的時候要給空，不然就是野指針了void RotateL(Node* parent)//左單旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;if (pparent == nullptr){subR->_parent = nullptr;_root = subR;}else{if (pparent->_left == parent){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent)//右單旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;if (pparent == nullptr){subL->_parent = nullptr;_root = subL;}else{if (pparent->_left == parent){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}parent->_bf = 0;subL->_bf = 0;}void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}void InOrder(Node* root){if (root == nullptr)return;InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;InOrder(root->_right);}public:void inorder(){InOrder(_root);}bool find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{return true;}}return false;}bool insert(const pair<K, V>& kv){if (_root == nullptr)//插入的時候要特殊處理空樹{_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;//如果已經(jīng)在，那就插入失敗，返回false}}//找到了，開始插入；cur = new Node(kv);cur->_parent = parent;if (kv.first > parent->_kv.first)//插入的節(jié)點(diǎn)很大，插在右邊{parent->_bf++;parent->_right = cur;}else{parent->_bf--;parent->_left = cur;}//插入完成，調(diào)整平衡因子；while (parent){if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//開始旋轉(zhuǎn)if (parent->_bf == 2 && cur->_bf == 1)//右邊太高了，左單旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1)//左邊太高了，右單旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//右邊高，但是偏了{(lán)Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateRL(parent);if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){subRL->_bf = subR->_bf = 0;parent->_bf = -1;}else if(bf == -1){subRL->_bf = parent->_bf = 0;subR->_bf = 1;}else{assert(false);}}else if (parent->_bf == -2 && cur->_bf == 1)//左邊高但是偏向右邊{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateLR(parent);if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = subLR->_bf = 0;}else if(bf == -1){subLR->_bf = subL->_bf = 0;parent->_bf = 1;}else{assert(false);}}}else{assert(false);//走到這里來就出現(xiàn)錯誤了}}return true;}};
}

---

對于AVL樹的刪除，和插入類似，但是更加復(fù)雜些，限于篇幅，就暫且不講AVL樹的刪除了，感興趣的讀者可以參考《算法導(dǎo)論》和《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）》（殷人昆版）。

---