0.前言

前面我們已經(jīng)學習過二叉搜索樹了，但如果我們是用二叉搜索樹來封裝map和set等關聯(lián)式容器是有缺陷的，很可能會退化為單分支的情況，那樣效率就極低了，那么有沒有方法來彌補二叉搜索樹的缺陷呢？

那么AVL樹就出現(xiàn)了，通過AVL樹的右單旋、左單旋、左右單旋，右左單旋等操作來防止二叉搜索樹退化為單分支的情況出現(xiàn)。

因此，兩位俄羅斯的數(shù)學家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問題的方法：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
AVL樹也是以這兩位大佬名字的首字母來命名的。

1.AVL樹的概念

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

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

我們這里使用的平衡因子是右子樹高度 - 左子樹高度。?

?

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

代碼如下：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//該節(jié)點的左孩子AVLTreeNode<K, V>* _right;	//該節(jié)點的右孩子AVLTreeNode<K, V>* _parent;	//該節(jié)點的雙親pair<K, V>  _kv;	//該節(jié)點的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//該節(jié)點初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};

3.AVL樹的插入

AVL樹就是在二叉搜索樹的基礎上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。那么
AVL樹的插入過程可以分為兩步：

1. 按照二叉搜索樹的方式插入新節(jié)點
2. 調(diào)整節(jié)點的平衡因子
   ?

插入思路：

?1.按照搜索樹規(guī)則插入

2.更新插入節(jié)點的祖先節(jié)點的平衡因子

? ? ? ? a.插入父親的右邊，父親的平衡因子--

? ? ? ? b.插入父親的左邊，父親的平衡因子++

? ? ? ? c.父親平衡因子 == 0， 父親所在子樹高度不變，不再繼續(xù)往上更新。插入結束

? ? ? ? d.父親平衡因子 == 1 or -1， 父親所在子樹高度變了，繼續(xù)往上更新。

? ? ? ? e.父親平衡因子 == 2 or -2， 父親所在子樹已經(jīng)不平衡了，需要旋轉(zhuǎn)處理。

更新中不可能出現(xiàn)其他值，插入之前樹是AVL樹，平衡因子要么是1 -1 0， ++ --

最多就是c/d/e三種情況。

?代碼如下：

	bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;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;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){//更新結束break;}else if (parent->_bf == -1 || parent->_bf == 1){//繼續(xù)往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){//當前子樹出現(xiàn)了問題，需要旋轉(zhuǎn)平衡一下if (parent->_bf == -2 && cur->_bf == -1){//右單旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左單旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右雙旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左雙旋//RotateRL(parent);}break;}else{//理論上不會出現(xiàn)這種情況，但仍要判斷，大佬都不能保證自己的代碼沒有bugassert(false);}}return true;}

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

4.1 右單旋

插入新節(jié)點要插入較高左子樹的左側（左左）-》右單旋

圖形解析：

?實現(xiàn)代碼如下：

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能為空，不為空時才能調(diào)整subLR的父節(jié)點subLR->_parent = parent;subL->_right = parent;//parent不一定就是根節(jié)點，也可能是子樹，所以要設置一個ppNode來標記parent的父節(jié)點Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

4.2 左單旋

插入新節(jié)點要插入較高右子樹的右側（右右）-》左單旋

圖形解析：

?代碼如下：

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能為空，不為空時才能調(diào)整subRL的父節(jié)點subRL->_parent = parent;subR->_left = parent;//parent不一定就是根節(jié)點，也可能是子樹，所以要設置一個ppNode來標記parent的父節(jié)點Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}

4.3 左右雙旋

插入新節(jié)點要插入較高左子樹的右側（左右）-》左右雙旋

圖形解析：

對于插入的位置根據(jù)h的高度和插入的位置時的平衡因子出現(xiàn)的最終的結果可分為三種情況：

1.h == 0

? ? ? ? 60自己就是新增節(jié)點。bf == 0

此時的平衡因子為，30 60 90節(jié)點都為0。

2.h > 0

? ? ? ? a.新增節(jié)點插入的是60的左子樹中 bf == -1

此時的平衡因子為，30節(jié)點為0,90為0,60為1

? ? ? ? b.新增節(jié)點插入的是60的右子樹中bf?== 1

此時的平衡因子為，30節(jié)點為-1,90為0,60為0

代碼如下：

?

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理論上不會出現(xiàn)的情況assert(false);}}

4.4 右左雙旋

插入新節(jié)點要插入較高右子樹的左側（右左）-》右左雙旋

與左右雙旋類似

代碼如下：

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理論上不會出現(xiàn)的情況assert(false);}}

總結：
假如以pParent為根的子樹不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮
1. pParent的平衡因子為2，說明pParent的右子樹高，設pParent的右子樹的根為pSubR
當pSubR的平衡因子為1時，執(zhí)行左單旋
當pSubR的平衡因子為-1時，執(zhí)行右左雙旋
2. pParent的平衡因子為-2，說明pParent的左子樹高，設pParent的左子樹的根為pSubL
當pSubL的平衡因子為-1是，執(zhí)行右單旋
當pSubL的平衡因子為1時，執(zhí)行左右雙旋
旋轉(zhuǎn)完成后，原pParent為根的子樹個高度降低，已經(jīng)平衡，不需要再向上更新。
?

5.AVL樹的驗證

5.1 驗證其是否為二叉搜索樹

給一個序列進行一次中序遍歷，看是否有序，有序即為二叉搜索樹。

void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}

5.2 驗證其是否為平衡樹

	bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//順便檢查一下平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->right);}

6.AVL樹的刪除（了解）

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

7.AVL樹的性能

AVL樹是一棵絕對平衡的二叉搜索樹，其要求每個節(jié)點的左右子樹高度差的絕對值都不超過1，這樣可以保證查詢時高效的時間復雜度，即logN。但是如果要對AVL樹做一些結構修改的操作，性能非常低下，比如：插入時要維護其絕對平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。因此：如果需要一種查詢高效且有序的數(shù)據(jù)結構，而且數(shù)據(jù)的個數(shù)為靜態(tài)的(即不會改變)，可以考慮AVL樹，但一個結構經(jīng)常修改，就不太適合。

?8.AVL樹的整體模擬代碼實現(xiàn)

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//該節(jié)點的左孩子AVLTreeNode<K, V>* _right;	//該節(jié)點的右孩子AVLTreeNode<K, V>* _parent;	//該節(jié)點的雙親pair<K, V>  _kv;	//該節(jié)點的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//該節(jié)點初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};template<class K, class V>
class 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;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;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更新平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){//更新結束break;}else if (parent->_bf == -1 || parent->_bf == 1){//繼續(xù)往上更新cur = parent;parent = parent->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){//當前子樹出現(xiàn)了問題，需要旋轉(zhuǎn)平衡一下if (parent->_bf == -2 && cur->_bf == -1){//右單旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//左單旋RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右雙旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左雙旋RotateRL(parent);}break;}else{//理論上不會出現(xiàn)這種情況，但仍要判斷，大佬都不能保證自己的代碼沒有bugassert(false);}}return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能為空，不為空時才能調(diào)整subLR的父節(jié)點subLR->_parent = parent;subL->_right = parent;//parent不一定就是根節(jié)點，也可能是子樹，所以要設置一個ppNode來標記parent的父節(jié)點Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能為空，不為空時才能調(diào)整subRL的父節(jié)點subRL->_parent = parent;subR->_left = parent;//parent不一定就是根節(jié)點，也可能是子樹，所以要設置一個ppNode來標記parent的父節(jié)點Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理論上不會出現(xiàn)的情況assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理論上不會出現(xiàn)的情況assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}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 leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//順便檢查一下平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}
void TestAVLTree2()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();cout << t1.IsBalance() << endl;
}