前言

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

---

一、AVL 樹介紹

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

??AVL樹是一棵二叉搜索樹，且高度平衡，因此AVL樹也叫高度平衡二叉搜索樹。如果AVL樹有n個(gè)結(jié)點(diǎn)，其 高度可保持在$O(lo{g}_{2}N)$，搜索時(shí)間復(fù)雜度$O(lo{g}_{2}N)$。

---

AVL樹的性質(zhì)

• 任意一顆子樹的左右子樹都是AVL樹
• 任意一顆子樹的左右子樹高度之差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過1

---

二、AVL樹節(jié)點(diǎn)的定義

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K, V>* _left;	// 該節(jié)點(diǎn)的左孩子AVLTreeNode<K, V>* _right;	// 該節(jié)點(diǎn)的右孩子AVLTreeNode<K, V>* _parent;	// 該節(jié)點(diǎn)的雙親pair<K, V> _kv;int _bf;					// 該節(jié)點(diǎn)的平衡因子
};

---

三、AVL樹的插入

AVL樹的插入過程可以分為兩步：

1. 先按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到AVL樹中
2. 新節(jié)點(diǎn)插入后，AVL樹的平衡性可能會(huì)遭到破壞，此時(shí)就需要更新平衡因子，并檢測(cè)是否破壞了AVL樹的平衡性。

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;// 找插入節(jié)點(diǎn)的位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 插入節(jié)點(diǎn)cur = new Node(kv);// 鏈接cur和parentif (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 控制平衡while (parent)	//最壞的情況是更新到根才會(huì)停止{// 更新平衡因子。新增在右，parent的平衡因子++ ；新增在左，parent的平衡因子--if (cur == parent->_right)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0)//更新后，parent的平衡因子為0，說明插入后兩邊一樣高，插入填入了矮的部分，parent所在子樹高度不變，不需要繼續(xù)往上更新。{break;}else if (abs(parent->_bf) == 1)//更新后，abs(parent的平衡因子)為1，說明插入后有一邊高，parent所在子樹高度變了，需要繼續(xù)往上更新。{parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 2)//更新后，abs(parent的平衡因子)為2，說明已經(jīng)打破平衡，parent所在子樹需要旋轉(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;	//一次插入只會(huì)有一次旋轉(zhuǎn)，旋轉(zhuǎn)完成了直接break}else //更新后，abs(parent的平衡因子)大于2，說明插入前就不是AVL樹，需要檢查之前的操作{assert(false);}}return true;
}

---

四、AVL樹的旋轉(zhuǎn)

旋轉(zhuǎn)原則：1. 旋轉(zhuǎn)為平衡樹 2. 保持搜索樹規(guī)則

---

新節(jié)點(diǎn)插入較高右子樹的右側(cè)—右右：左單旋

// 新節(jié)點(diǎn)插入較高右子樹的右側(cè)---右右：左單旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)						//subRL可能為空subRL->_parent = parent;Node* ppNode = parent->_parent; //注意：有可能parent不是根節(jié)點(diǎn)，保存上一層節(jié)點(diǎn)subR->_left = parent;parent->_parent = subR;if (_root == parent)			//parent是整棵樹的根{_root = subR;subR->_parent = nullptr;}else                            //parent是子樹的根{if (ppNode->_left == parent)//判斷上一層節(jié)點(diǎn)和parent的關(guān)系{ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;	//修改平衡因子
}

---

新節(jié)點(diǎn)插入較高左子樹的左側(cè)—左左：右單旋

// 新節(jié)點(diǎn)插入較高左子樹的左側(cè)---左左：右單旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;
}

---

新節(jié)點(diǎn)插入較高左子樹的右側(cè)—左右：先左單旋再右單旋

??在b或者c的位置插入，都會(huì)引起bf的變化，引發(fā)雙旋。將雙旋變成單旋后再旋轉(zhuǎn)，即：先對(duì)30進(jìn)行左單旋，然后再對(duì)90進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。

// 新節(jié)點(diǎn)插入較高左子樹的右側(cè)---左右：先左單旋再右單旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;	//記錄subLR的平衡因子，根據(jù)它的大小將其他平衡因子的更新分為三種情況RotateL(parent->_left); // 先cur左旋再parent右旋RotateR(parent);subLR->_bf = 0;if (bf == 1)			// c插入{parent->_bf = 0;subL->_bf = -1;}else if (bf == -1)		// b插入{parent->_bf = 1;subL->_bf = 0;}else if (bf == 0)		//a,b,c,d為空樹，subLR為新增{parent->_bf = 0;subL->_bf = 0;}else					// 說明出問題了{assert(false);}
}

---

新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左：先右單旋再左單旋

整體思路同上：

//新節(jié)點(diǎn)插入較高右子樹的左側(cè)——右左：先右單旋再左單旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}
}

---

總結(jié)

??假如以Parent為根的子樹不平衡，即Parent的平衡因子為2或者-2，分以下情況考慮：

1. Parent的平衡因子為2，說明Parent的右子樹高，設(shè)Parent的右子樹的根為SubR。當(dāng)SubR的平衡因子為1時(shí)，執(zhí)行左單旋。當(dāng)SubR的平衡因子為-1時(shí)，執(zhí)行右左雙旋。
2. Parent的平衡因子為-2，說明Parent的左子樹高，設(shè)Parent的左子樹的根為SubL。當(dāng)SubL的平衡因子為-1是，執(zhí)行右單旋。當(dāng)SubL的平衡因子為1時(shí)，執(zhí)行左右雙旋。

??旋轉(zhuǎn)完成后，原Parent為根的子樹個(gè)高度降低，已經(jīng)平衡，不需要再向上更新。

---

旋轉(zhuǎn)的意義

1. 平衡
2. 降高度

---

五、AVL樹的驗(yàn)證

驗(yàn)證其為二叉搜索樹

??如果中序遍歷可得到一個(gè)有序的序列，就說明為二叉搜索樹

public:void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}

---

驗(yàn)證其為平衡樹

??每個(gè)節(jié)點(diǎn)子樹高度差的絕對(duì)值不超過1，節(jié)點(diǎn)的平衡因子是否計(jì)算正確

public：bool IsBalance(){return _IsBalance(_root);}private:int Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;} bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}

---

六、AVL樹的刪除

??因?yàn)锳VL樹也是二叉搜索樹，可按照二叉搜索樹的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不錯(cuò)與刪除不同的時(shí)，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。

---

七、AVL樹的性能

??AVL樹是一棵絕對(duì)平衡的二叉搜索樹，其要求每個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值都不超過1，這樣可以保證查詢時(shí)高效的時(shí)間復(fù)雜度為$O(lo{g}_{2}N)$。

??但是如果要對(duì)AVL樹做一些結(jié)構(gòu)修改的操作，性能非常低下，比如：插入時(shí)要維護(hù)其絕對(duì)平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時(shí)，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。

??因此：如果需要一種查詢高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個(gè)數(shù)為靜態(tài)的，可以考慮AVL樹，但一個(gè)結(jié)構(gòu)經(jīng)常修改，就不太適合。

---

八、AVL樹的實(shí)現(xiàn)

#include<iostream>
#include<assert.h>
#include <map>
#include <string>
#include <algorithm>
#include<time.h>
#include <assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K, V>* _left;	// 該節(jié)點(diǎn)的左孩子AVLTreeNode<K, V>* _right;	// 該節(jié)點(diǎn)的右孩子AVLTreeNode<K, V>* _parent;	// 該節(jié)點(diǎn)的雙親pair<K, V> _kv;int _bf;					// 該節(jié)點(diǎn)的平衡因子
};template<class K, class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;// 找插入節(jié)點(diǎn)的位置while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 插入節(jié)點(diǎn)cur = new Node(kv);// 鏈接cur和parentif (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 控制平衡while (parent)	//最壞的情況是更新到根才會(huì)停止{// 更新平衡因子。新增在右，parent的平衡因子++ ；新增在左，parent的平衡因子--if (cur == parent->_right)parent->_bf++;elseparent->_bf--;if (parent->_bf == 0)//更新后，parent的平衡因子為0，說明插入后兩邊一樣高，插入填入了矮的部分，parent所在子樹高度不變，不需要繼續(xù)往上更新。{break;}else if (abs(parent->_bf) == 1)//更新后，abs(parent的平衡因子)為1，說明插入后有一邊高，parent所在子樹高度變了，需要繼續(xù)往上更新。{parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 2)//更新后，abs(parent的平衡因子)為2，說明已經(jīng)打破平衡，parent所在子樹需要旋轉(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;	//一次插入只會(huì)有一次旋轉(zhuǎn)，旋轉(zhuǎn)完成了直接break}else //更新后，abs(parent的平衡因子)大于2，說明插入前就不是AVL樹，需要檢查之前的操作{assert(false);}}return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}
private:bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "平衡因子異常" << endl;return false;}return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}int Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}// 新節(jié)點(diǎn)插入較高右子樹的右側(cè)---右右：左單旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)						//subRL可能為空subRL->_parent = parent;Node* ppNode = parent->_parent; //注意：有可能parent不是根節(jié)點(diǎn)，保存上一層節(jié)點(diǎn)subR->_left = parent;parent->_parent = subR;if (_root == parent)			//parent是整棵樹的根{_root = subR;subR->_parent = nullptr;}else                            //parent是子樹的根{if (ppNode->_left == parent)//判斷上一層節(jié)點(diǎn)和parent的關(guān)系{ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;	//修改平衡因子}// 新節(jié)點(diǎn)插入較高左子樹的左側(cè)---左左：右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}// 新節(jié)點(diǎn)插入較高左子樹的右側(cè)---左右：先左單旋再右單旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;	//記錄subLR的平衡因子，根據(jù)它的大小將其他平衡因子的更新分為三種情況RotateL(parent->_left); // 先cur左旋再parent右旋RotateR(parent);subLR->_bf = 0;if (bf == 1)			// c插入{parent->_bf = 0;subL->_bf = -1;}else if (bf == -1)		// b插入{parent->_bf = 1;subL->_bf = 0;}else if (bf == 0)		//a,b,c,d為空樹，subLR為新增{parent->_bf = 0;subL->_bf = 0;}else					// 說明出問題了{assert(false);}}//新節(jié)點(diǎn)插入較高右子樹的左側(cè)——右左：先右單旋再左單旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;}else{assert(false);}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}
private:Node* _root = nullptr;
};void TestAVLTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 測(cè)試雙旋平衡因子調(diào)節(jié)//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> t1;for (auto e : a){t1.Insert(make_pair(e, e));}t1.InOrder();cout << "IsBalance:" << t1.IsBalance() << endl;
}void TestAVLTree2()
{size_t N = 10000;srand(time(0));AVLTree<int, int> t1;for (size_t i = 0; i < N; ++i){int x = rand();t1.Insert(make_pair(x, i));}cout << "IsBalance:" << t1.IsBalance() << endl;
}