我們上期提到了二叉搜索樹(shù)，只是簡(jiǎn)單的講了一下原理，那么今天我們就講一下AVL樹(shù)。

AVL樹(shù)的概念

其實(shí)大家應(yīng)該很奇怪，難道二叉搜索樹(shù)不能存儲(chǔ)數(shù)據(jù)嗎？為什么要有AVL樹(shù)呢？二叉搜索樹(shù)有可能會(huì)有畸形的情況。像下圖，數(shù)據(jù)比較分散的話，這棵樹(shù)很正常，如果我們插入的數(shù)相對(duì)有序就會(huì)變成右邊那樣畸形的樹(shù)。

這個(gè)時(shí)候就需要人工干預(yù)，這里的AVL數(shù)就可以更好的控制這個(gè)情況，它有自己的平衡規(guī)則：左右子樹(shù)高度之差(平衡因子)絕對(duì)不超過(guò)1(-1,0,1)。如果不滿足這個(gè)規(guī)則，那么我們就旋轉(zhuǎn)。

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

因?yàn)锳VL樹(shù)也是二叉搜索樹(shù)的一種，所以他也要滿足二叉搜索樹(shù)的條件，然后在滿足他自己的平衡規(guī)則。

AVL樹(shù)的架構(gòu)

其實(shí)數(shù)的節(jié)點(diǎn)架構(gòu)和整體架構(gòu)并沒(méi)有變，只是多了一個(gè)bf(平衡因子)，用來(lái)調(diào)節(jié)平衡。

struct AVLTreeNode
{AVLTreeNode(const pair<K, V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair<K, V> _kv;int _bf;
};
template<class K,class V>
class AVLTree
{public:typedef AVLTreeNode<K,V> Node;private:Node* _root=nullptr;
}

insert插入

引用pair對(duì)象

這里與原來(lái)不同，這里我們引入了一個(gè)pair對(duì)象，那么pair是什么？我們用pair來(lái)實(shí)現(xiàn)KV結(jié)構(gòu)，在庫(kù)中的map也是用pair也完成KV結(jié)構(gòu)的，所以這里我們就用這pair。pair對(duì)象的first是K值，second是V值。

引進(jìn)parent指針

這里引用父指針是因?yàn)槲覀儗?lái)要旋轉(zhuǎn)，要不斷向上調(diào)節(jié)平衡因子，因?yàn)楫?dāng)我們插入某個(gè)值有可能引起平衡因子失衡。

僅插入數(shù)據(jù)

其實(shí)插入部分和我們之前寫(xiě)的一樣，只不過(guò)要注意的是，我們的值存的是pair對(duì)象，要像拿到K值需要 _kv.first拿到K值。一定要遵循二叉搜索樹(shù)的規(guī)律，左子樹(shù)比根小，右子樹(shù)比根大。

	if (_root == nullptr){//插入第一個(gè)值Node* newNode = new Node(kv);_root = newNode;return true;}Node* newNode = new Node(kv);Node* cur = _root;Node* parent = cur;while (cur){if (cur->_kv.first < newNode->_kv.first){//大于在右邊parent = cur;cur = cur->_right;}else if (cur->_kv.first > newNode->_kv.first){//小于在左邊parent = cur;cur = cur->_left;}else{//等于,二叉搜索樹(shù)不允許冗余，所以直接返回false。return false;}}if (parent->_kv.first > newNode->_kv.first){//在左邊parent->_left = newNode;}else{//在右邊parent->_right = newNode;}newNode->_parent = parent;

調(diào)節(jié)平衡因子

情況1：插入在父親的右邊，父親的平衡因子++后為0

紅色是我插入的數(shù)，插入后，它的parent：12從-1加加后變成了0，我們還需要向上更新嗎？答案是不需要向上更新，為什么？0表示左右子樹(shù)的高度差為0，也就說(shuō)高度沒(méi)有變，所以我不需要再向上更新。
解釋：平衡因子原來(lái)是1/-1都表示這個(gè)樹(shù)缺了一個(gè)節(jié)點(diǎn)，當(dāng)我們插入之后正好填上了這個(gè)節(jié)點(diǎn)，但是高度并不變?？磮D！我把15插入，右子樹(shù)這個(gè)高度沒(méi)有變。

情況2：插入在父親的左邊，父親的平衡因子–后為0

當(dāng)我插入在左邊，那我們就需要給父親的因子bf–。

情況3：插入左或者右，恰巧父親不是0，是-1/1

父親的平衡因子==1/-1，父親所在子樹(shù)高度變了。高度變了繼續(xù)向上更新。

情況4：當(dāng)父親的平衡因子==-2/2，不需要在更新了，證明不平衡了，需要旋轉(zhuǎn)。

這個(gè)時(shí)候就不滿足AVL樹(shù)的規(guī)則了，就需要旋轉(zhuǎn)。

左邊高，右旋

這個(gè)樹(shù)就是左邊高的情況，你會(huì)發(fā)現(xiàn)parent為-2，cur為-1，這個(gè)情況就是左邊比右邊要高，那么我們需要右旋。

右旋的口訣：把cur的右邊給parent的左邊，cur的右邊鏈接parent，在讓parent的parent鏈接cur。會(huì)發(fā)現(xiàn)我們把原來(lái)的parent變成了cur的右邊。并且現(xiàn)在是平衡的。

其實(shí)為什么要把cur的右邊給parent呢？是因?yàn)閏ur的右邊時(shí)當(dāng)前樹(shù)最大的值，cur給了parent鏈接到左邊，依然不會(huì)破壞二叉搜索樹(shù)的規(guī)則。

void RotateR(Node* parent )
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;
}

右邊高，左旋

當(dāng)我們插入紅色節(jié)點(diǎn)的時(shí)候就會(huì)導(dǎo)致右邊過(guò)高，那么我們就需要左旋。

左旋的口訣：讓cur的左邊給parent的右邊鏈接，然后讓父親變成cur的左邊。
解釋：為什么要把cur左邊的值給parent的右邊？cur當(dāng)前位置是parent的右邊，cur的左邊也是比parent大的值，給parent的右邊依然不影響二叉搜索樹(shù)的規(guī)則。

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* pphead = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pphead->_parent == parent){pphead->_right = subR;}else{pphead->_left = subR;}subR->_parent = pphead;}subR->_bf = parent->_bf = 0;
}

雙旋轉(zhuǎn)

還有一種情況，它并不是單純的一邊高，用單旋并不能解決問(wèn)題。當(dāng)我們僅僅只是單旋會(huì)發(fā)現(xiàn)他有變成了形態(tài)不同，但是問(wèn)題一樣的情況，這個(gè)時(shí)候就需要雙旋。

右左旋轉(zhuǎn)：先右旋然后左旋。

既然我們單旋解決不了問(wèn)題，我們可以把他變成一邊高，然后進(jìn)行單旋。
如這個(gè)圖，我們可以對(duì)subR進(jìn)行右旋后，在對(duì)parent左旋就可以了。

右左雙旋后：

但是有個(gè)問(wèn)題，平衡因子我們應(yīng)該如何更新？你可能會(huì)說(shuō)這種情況不是正好滿足左旋/右旋后平衡因子變成0嗎？但是如果其他位置都有節(jié)點(diǎn)呢？接下來(lái)我們抽象圖，給大家演示一下。
當(dāng)我們插入節(jié)點(diǎn)的位置不同，你會(huì)發(fā)現(xiàn)每一個(gè)平衡因子也不一樣。如圖：我插在了右邊。這個(gè)時(shí)候我通過(guò)右左雙旋就會(huì)得到下圖。如最右圖的紅色平衡因子，應(yīng)該變成這個(gè)情況。所以說(shuō)插入的位置不同，平衡因子也會(huì)不同。

如圖：假如我插在了左邊。會(huì)發(fā)現(xiàn)平衡因子又不一樣了。所以我們并不能用一個(gè)例子來(lái)概括所有。

那么我們應(yīng)該怎么做呢？其實(shí)從我們畫(huà)圖，你會(huì)發(fā)現(xiàn)我們改變的只不過(guò)是parent 、subR、sunRL這三個(gè)節(jié)點(diǎn)的因子，其他的并沒(méi)有改變。并且，跟subRL的因子有密切關(guān)系，所以我們只需要判斷subRL的因子是0/1/-1就能修改他們?nèi)齻€(gè)因子。

		void RotateRL(Node* parent){//右左雙旋//平衡因子需要自己調(diào)節(jié)Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0){//新插入的parent->_bf =0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){//右邊插入的subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if(bf==-1){//在左邊插入的parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}

左右雙旋：先左旋，在右旋。

圖下是：左右雙旋。

當(dāng)然了，我們依然需要分析平衡因子，所以我們依然要分析插入在哪個(gè)位置。
如圖：當(dāng)插入在右邊。

如圖：當(dāng)我們插在左邊。

		void RotateLR(Node* parent){//左右雙旋//平衡因子需要單獨(dú)調(diào)節(jié)Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//先左旋在右旋RotateL(parent->_left);RotateR(parent);//重新計(jì)算調(diào)節(jié)因子if (bf == 0){//當(dāng)且節(jié)點(diǎn)就是新插的subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else if(bf==1){//在當(dāng)前節(jié)點(diǎn)的右邊插入的parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if(bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else{assert(false);}}

中序遍歷

因?yàn)槎嫠阉鳂?shù)我們都是中序遍歷，因?yàn)橹行虮闅v更接近有序。

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

判斷是否平衡

什么時(shí)候不平衡？是不是因子大于等于2的時(shí)候，所以我們需要算左右樹(shù)的高度相減，如果超過(guò)2，那就是不平衡。

		bool _isBalance(Node* root){if (root == nullptr){return true;}int left = _Height(root->_left);int right = _Height(root->_right);if (abs(left - right) >= 2) return false;//因子大于等于2的時(shí)候不平衡return _isBalance(root->_left) && _isBalance(root->_right);}int _Height(Node* root){if (root == nullptr)return 0;int left = _Height(root->_left);int right = _Height(root->_right);return max(left, right) + 1;}

AVL樹(shù)整體代碼

以下是整個(gè)AVL樹(shù)所有的代碼？

問(wèn)題：為什么沒(méi)有像庫(kù)一樣寫(xiě)刪除呢？答：我們模擬實(shí)現(xiàn)其實(shí)是為了了解底層，并不是要超過(guò)底層，因?yàn)楝F(xiàn)有的庫(kù)已經(jīng)很好了，我們沒(méi)必要寫(xiě)一個(gè)。二叉搜索樹(shù)很少用刪除接口。所以這里沒(méi)有實(shí)現(xiàn)。

#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<assert.h>using namespace std;
namespace KV
{template<class K,class V>struct AVLTreeNode{AVLTreeNode(const pair<K, V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair<K, V> _kv;int _bf;};template<class K,class V>class AVLTree{public:typedef AVLTreeNode<K,V> Node;bool insert(const pair<K, V> kv){if (_root == nullptr){//插入第一個(gè)值Node* newNode = new Node(kv);_root = newNode;return true;}Node* newNode = new Node(kv);Node* cur = _root;Node* parent = cur;while (cur){if (cur->_kv.first < newNode->_kv.first){//大于在右邊parent = cur;cur = cur->_right;}else if (cur->_kv.first > newNode->_kv.first){//小于在左邊parent = cur;cur = cur->_left;}else{//等于,二叉搜索樹(shù)不允許冗余，所以直接返回false。return false;}}if (parent->_kv.first > newNode->_kv.first){//在左邊parent->_left = newNode;}else{//在右邊parent->_right = newNode;}newNode->_parent = parent;cur = newNode;while (parent){if (parent->_left == cur){cur->_parent->_bf--;}else if (parent->_right == cur){cur->_parent->_bf++;}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){//出現(xiàn)健康問(wèn)題需要旋轉(zhuǎn)//左邊高，右旋轉(zhuǎn)if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//右邊高，左旋轉(zhuǎn)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);}else{assert(false);}}else{//按道理說(shuō)不可能有這種情況，但是保不準(zhǔn)會(huì)有bugassert(false);break;}}return true;}void Inorder(){_Inorder(_root);}int Height(){return _Height(_root);}bool isBalance(){return _isBalance(_root);}private:int _Height(Node* root){if (root == nullptr)return 0;int left = _Height(root->_left);int right = _Height(root->_right);return max(left, right) + 1;}bool _isBalance(Node* root){if (root == nullptr){return true;}int left = _Height(root->_left);int right = _Height(root->_right);if (abs(left - right) >= 2) return false;return _isBalance(root->_left) && _isBalance(root->_right);}void RotateRL(Node* parent){//右左雙旋//平衡因子需要自己調(diào)節(jié)Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 0){//新插入的parent->_bf =0;subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){//右邊插入的subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if(bf==-1){//在左邊插入的parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){//左右雙旋//平衡因子需要單獨(dú)調(diào)節(jié)Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//先左旋在右旋RotateL(parent->_left);RotateR(parent);//重新計(jì)算調(diào)節(jié)因子if (bf == 0){//當(dāng)且節(jié)點(diǎn)就是新插的subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else if(bf==1){//在當(dāng)前節(jié)點(diǎn)的右邊插入的parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if(bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else{assert(false);}}void RotateR(Node* parent ){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* pphead = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pphead->_parent == parent){pphead->_right = subR;}else{pphead->_left = subR;}subR->_parent = pphead;}subR->_bf = parent->_bf = 0;}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second<<" 因子：" <<root->_bf<< endl;_Inorder(root->_right);}Node* _root=nullptr;};
}