---

前言

前面對map/multimap/set/multiset進行了簡單的介紹，在其文檔介紹中發(fā)現(xiàn)，這幾個容器有個共同點是：其底層都是按照二叉搜索樹來實現(xiàn)的，但是二叉搜索樹有其自身的缺陷，假如往樹中插入的元素有序或者接近有序，二叉搜索樹就會退化成單支樹，時間復雜度會退化成O(N)，因此map、set等關(guān)聯(lián)式容器的底層結(jié)構(gòu)是對二叉樹進行了平衡處理，即采用平衡二叉樹樹來實現(xiàn)。

1.AVL樹的概念

AVL樹，又稱平衡二叉搜索樹。二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。因此，兩位俄羅斯的數(shù)學家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，左右子樹的高度差被稱為平衡因子（平衡因子=右子樹高度-左子樹高度)，即可降低樹的高度，從而減少平均搜索長度。

AVL樹可以是一棵空樹，也可能是具有一下性質(zhì)的一棵平衡二叉樹：

• 樹的左右子樹都是一棵AVL樹
• 樹的左右子樹高度之差（平衡因子）的絕對值不超過1（可以是-1,0，1）

如果一棵二叉樹是高度平衡的，它就是AVL樹，如果它有n個結(jié)點，其高度可保持在O(logN),搜索時間復雜度為O(NlogN)。

2.AVL樹節(jié)點的定義

我們需要實現(xiàn)一個KV模型的AVL樹，在這里最好定義成三叉鏈的結(jié)構(gòu)，多引入一個_parent（父節(jié)點），方便后序插入等操作。除此之外還要在每個結(jié)點中引入平衡因子，由于新構(gòu)造的結(jié)點的左右子樹均為空樹，所以初始化的時候?qū)⑵胶庖蜃釉O置為0就好。

為什么要設置平衡因子？為什么要設置成三叉鏈結(jié)構(gòu)？

由于我們插入結(jié)點后需要倒著往上進行平衡因子的更新，所以我們將AVL樹結(jié)點的結(jié)構(gòu)設置為了三叉鏈結(jié)構(gòu)，這樣我們就可以通過父指針找到其父結(jié)點，進而對其平衡因子進行更新。當然，我們也可以不用三叉鏈結(jié)構(gòu)，可以在插入結(jié)點時將路徑上的結(jié)點存儲到一個棧當中，當我們更新平衡因子時也可以通過這個棧來更新祖先結(jié)點的平衡因子，但是相對較麻煩。

注意平衡因子不是必須的，它只是AVL樹其中一種實現(xiàn)方式，采用其它方法也可以判斷左右子樹高度差絕對值是否小于等于1，但是我認為引入平衡因子可以給我們更加直觀的呈現(xiàn)平衡二叉樹的整體特征。

//定義AVL樹的結(jié)點
//三叉鏈+平衡因子
template<class K,class V>
struct AVLTreeNode
{//存儲<key,value>數(shù)據(jù)的結(jié)點pairpair<K,V> _kv;//三叉鏈AVLTreeNode<K, V>* _parent;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;int _bf;//平衡因子=右子樹高度-左子樹高度（-1,0,1）//結(jié)點的構(gòu)造函數(shù)AVLTreeNode(const pair<K,V>& kv):_kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr),_bf(0){}
};

3.AVL樹的插入

思路：

1. 插入數(shù)據(jù)到平衡二叉樹中，我們首先需要一個根
2. 按照二叉搜索樹的插入方法，找到待插入位置。
   待插入結(jié)點的key值比當前結(jié)點小就插入到該結(jié)點的左子樹。
   待插入結(jié)點的key值比當前結(jié)點大就插入到該結(jié)點的右子樹。
   待插入結(jié)點的key值與當前結(jié)點的key值相等就插入失敗。
3. 找到待插入位置后，將待插入結(jié)點插入到樹中。（注意保持三叉鏈結(jié)構(gòu)）
4. 更新平衡因子： 一個結(jié)點的平衡因子是否需要更新，是取決于該結(jié)點的左右子樹的高度是否發(fā)生了變化，因此插入一個結(jié)點后，該結(jié)點的祖先結(jié)點的平衡因子可能也需要更新。
   新增結(jié)點在parent的右邊，parent的平衡因子+ + 。
   新增結(jié)點在parent的左邊，parent的平衡因子? ? 。

每更新完一個結(jié)點的平衡因子后，還需要再進行以下判斷：

如果parent的平衡因子等于-1或者1，表明還需要繼續(xù)往上更新平衡因子。
如果parent的平衡因子等于0，表明無需繼續(xù)往上更新平衡因子了。
如果parent的平衡因子等于-2或者2，表明此時以parent結(jié)點為根結(jié)點的子樹已經(jīng)不平衡了，需要進行旋轉(zhuǎn)處理。

注意： parent的平衡因子在更新前只可能是-1/0/1（AVL樹中每個結(jié)點的左右子樹高度之差的絕對值不超過1）。

跳出循環(huán)的條件

在最壞情況下，平衡因子時一路更新到根結(jié)點。直到找到與待插入結(jié)點的key值相同的結(jié)點判定為插入失敗，或者最終走到空樹位置進行結(jié)點插入。所以循環(huán)的條件是parent不為空，這也是使用三叉鏈結(jié)構(gòu)的原因，我們可以迭代著往上走。

插入代碼如下：

template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://插入函數(shù):我們需要將給的pair數(shù)據(jù)插入到AVL樹中。bool insert(const pair<K, V>& kv){//1.插入數(shù)據(jù)到平衡二叉樹中，我們首先需要一個根if (_root == nullptr){_root = new Node(kv);return true;}//2.根據(jù)二叉搜索樹的特性（小的往左走，大的往右走），找到適合插入的位置Node* parent = nullptr;Node* cur = _root;//從根開始找合適的位置while (cur){//注意：在平衡二叉搜索樹中，鍵值對pair是按key值進行比較的if (cur->_kv.first < kv.first){cur = cur->_right;parent = cur;}else if (cur->_kv.first > kv.first){cur = cur->_left;parent = cur;}else{return false;//相等直接返回false}}//3.插入結(jié)點，注意保持三叉鏈的鏈接//此時parent指向待插入結(jié)點位置的父節(jié)點cur = new Node(kv);if (parent->_kv.first>kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 1、更新平衡因子while (parent) // parent為空，也就更新到根{// 新增在右，parent->bf++;// 新增在左，parent->bf--;if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}// 是否繼續(xù)更新依據(jù)：子樹的高度是否變化// 1、parent->_bf == 0說明之前parent->_bf是 1 或者 -1// 說明之前parent一邊高一邊低，這次插入填上矮的那邊，parent所在子樹高度不變，不需要繼續(xù)往上更新// 2、parent->_bf == 1 或 -1 說明之前是parent->_bf == 0，兩邊一樣高，現(xiàn)在插入一邊更高了，// parent所在子樹高度變了，繼續(xù)往上更新// 3、parent->_bf == 2 或 -2，說明之前parent->_bf == 1 或者 -1，現(xiàn)在插入嚴重不平衡，違反規(guī)則// 就地處理--旋轉(zhuǎn)// 旋轉(zhuǎn)：// 1、讓這顆子樹左右高度不超過1// 2、旋轉(zhuǎn)過程中繼續(xù)保持他是搜索樹// 3、更新調(diào)整孩子節(jié)點的平衡因子// 4、讓這顆子樹的高度跟插入前保持一致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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}
private:Node* _root = nullptr;
};

4.AVL樹的旋轉(zhuǎn)

在AVL樹的插入中，我們提到若是在更新平衡因子的過程當中，出現(xiàn)了平衡因子為-2/2的結(jié)點，這時我們需要對以該結(jié)點為根結(jié)點的樹進行旋轉(zhuǎn)處理。平衡二叉搜索樹的旋轉(zhuǎn)有多種，分別是左單旋，右單旋，左右雙旋，右左雙旋，我們分別介紹。

旋轉(zhuǎn)的目的：

• 讓這棵樹的左右子樹高度差的絕對值不超過1
• 旋轉(zhuǎn)過程中依然要保存AVL樹的特性
• 更新被調(diào)整的結(jié)點的平衡因子
• 讓這棵子樹的高度跟插入當前結(jié)點之前的高度一致

左單旋

1.什么情況下進行的是左單旋？

單純的右邊高，當前的parent的平衡因子==2,其右孩子的平衡因子為1，即cur的平衡因子為1的時候進行做單旋。 我們就需要把左邊壓下來。

if (parent->_bf == 2 && cur->_bf == 1)
{RotateL(parent);
}

2.如何進行左單旋？

為了提高代碼的可閱讀性，我們進行一下命名：當前parent指向30，subR（右子樹）指向60，subRL（右子樹的左子樹）指向b。

步驟：

1. SubR的左子樹作為parent的右子樹（這里要注意完善三叉鏈的連接,勿忘_parent,所以這里有一個注意事項，就是進行subRL->_parent的時候，需要判斷subRL是否為空）；
2. 讓parent作為subR的左子樹；
3. 讓subR作為整個子樹的根（注意這里要判斷subR是子樹的根，還是整棵樹的root）
4. 更新平衡因子。

代碼實現(xiàn)：

//左單旋void RotateL(Node* parent){//命名結(jié)點Node* subR = parent->_right;Node* subRL = subR->_left;//若parent是某棵子樹，則要保留當前結(jié)點的父節(jié)點，這樣旋轉(zhuǎn)之后subR成為根，才能和這棵樹連成整體Node* ppNode = parent->_parent;//1.將subR的左子樹給到parent的右子樹parent->_right = subRL;if (subRL)//注意subRL不為空，才能進行這步，否則會造成對空指針解引用的錯誤{//完善三叉鏈的連接subRL->_parent = parent;}//2.將parent給到subR的左子樹，subR變成當前子樹的根subR->_left = parent;parent->_parent = subR;//3.將旋轉(zhuǎn)完的子樹；連接回去if (ppNode == nullptr){//如果ppNode為空，則subR就是當前這棵樹的根了_root = subR;subR->_parent = nullptr;}else{//如果剛開始parent是左子樹if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}//更新平衡因子parent->_bf = subR->_bf = 0;}

右單旋

1,什么情況下進行右單旋？

單純的左邊高，當前parent的平衡因子== -2,parent左節(jié)點的平衡因子等于-1,即cur的平衡因子為-1，我們就需要把右邊壓下來。

if (parent->_bf == -2 && cur->_bf == -1)
{RotateR(parent);
}

2,如何進行右單旋？

步驟：

1. 讓subL的右子樹作為parent的左子樹；
2. 讓parent作為subL的右子樹；
3. 讓subL作為整個子樹的根；
4. 更新平衡因子。

void RotateR(Node* parent){//命名結(jié)點Node* subL = parent->_left;Node* subLR = subL->_right;//若parent是某棵子樹，則要保留當前結(jié)點的父節(jié)點，這樣旋轉(zhuǎn)之后subL成為根，才能和這棵樹連成整體Node* ppNode = parent->_parent;//1.將subL的右子樹給到parent的左子樹parent->_left = subLR;if (subLR)//注意subRL不為空，才能進行這步，否則會造成對空指針解引用的錯誤{//完善三叉鏈的連接subLR->_parent = parent;}//2.將parent給到subL的右子樹，subL變成當前子樹的根subL->_right = parent;parent->_parent = subL;//3.將旋轉(zhuǎn)完的子樹；連接回去if (ppNode == nullptr){//如果ppNode為空，則subR就是當前這棵樹的根了_root = subL;subL->_parent = nullptr;}else{//如果剛開始parent是左子樹if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//更新平衡因子parent->_bf = subL->_bf = 0;}

左右雙旋

1.什么情況下進行左右雙旋？

不難發(fā)現(xiàn)，前面講的左單旋和右單旋，它們觸發(fā)旋轉(zhuǎn)的圖形是一條直線，所以當圖中出現(xiàn)折線型的路徑時，就會觸發(fā)雙旋。

2.如何進行左右雙旋？

步驟：

1. 以subL為軸點進行左單旋（經(jīng)過左單旋后，由圖可以發(fā)現(xiàn)，折線型的路徑變成了直線型）；
2. 以parent為軸點進行右單旋（當出現(xiàn)直線型的路徑時，再進行一次單旋即可）；
3. 更新平衡因子：這是最復雜的一步，我們畫的圖是在b處插入新的結(jié)點，旋轉(zhuǎn)成功后，subL和subLR的平衡因子更新為0，parent的平衡因子變成了1。如果我們是在c處插入新的結(jié)點，那么結(jié)果又是不同的（這里大家可以自己嘗試著換一下旋轉(zhuǎn)過程圖）。

左右雙旋后，平衡因子的更新隨著subLR原始平衡因子的不同分為以下三種情況：
在插入結(jié)點后，先記錄一下subLR的平衡因子，若平衡因子為-1，則是在b處進行插入，最后subL和subR的平衡因子更新為0，parent的平衡因子變成了1；

若平衡因子為1，則是在c處進行插入，最后subLR和parent的平衡因子更新為0，subL的平衡因子變成了-1；

當subLR原始平衡因子是0時，左右雙旋后parent、subL、subLR的平衡因子分別更新為0、0、0。

代碼實現(xiàn)：

//左右雙旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//以subL為軸點進行左單旋，左邊往下壓RotateL(parent->_left);//以parent為軸點進行右單旋，右邊往下壓RotateR(parent);//更新平衡因子if (bf == 1)//subLR右子樹新增結(jié)點{parent->_bf= 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}

右左雙旋

步驟：

1. 以subR為旋轉(zhuǎn)點進行右單旋。
2. 以parent為旋轉(zhuǎn)點進行左單旋。
3. 更新平衡因子。

//右左雙旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//1、以subR為軸進行右單旋RotateR(subR);//2、以parent為軸進行左單旋RotateL(parent);//3、更新平衡因子if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else{assert(false); //在旋轉(zhuǎn)前樹的平衡因子就有問題}
}

AVL樹的驗證

AVL樹是在二叉搜索樹的基礎上加入了平衡的限制，因此要驗證AVL樹，可以分兩步：

1.驗證其為二叉搜索樹
如果中序遍歷得到的是一個有序的序列，就說明它是一棵二叉搜索樹

2.驗證其為平衡樹
右子樹的高度-左子樹的高度絕對值小于等于1
結(jié)點的平衡因子是否計算正確

代碼實現(xiàn)：

void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}

AVL樹的刪除

可按照二叉搜索樹的方式將節(jié)點刪除，然后再更新平衡因子，最差情況下要一直調(diào)整到根節(jié)點。

具體實現(xiàn)可參考《算法導論》或《數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο蠓椒ㄅcC++描述》殷人昆版。

AVL樹的性能

AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個結(jié)點的左右子樹高度差的絕對值小于等于1，這樣可以保證訪問時的時間復雜度,O(logN),但是如果要對AVL樹作一些結(jié)構(gòu)修改的操作，性能就會降低。比如：插入時，我們需要維護其平衡，旋轉(zhuǎn)的次數(shù)就比較多，在最差的情況下，還有可能要一直旋轉(zhuǎn)到根。因此，如果需要一直查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個數(shù)是不變的，可以考慮AVL樹，但如果一個結(jié)構(gòu)經(jīng)常需要修改，就不適合用AVL樹。

---