一.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ì)的二叉搜索樹：

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

具有以上性質(zhì)的樹被稱為AVL樹。

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

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

template<class K,class V>
struct AVLTreeNode
{ALVTreeNode<K,V>* _left;AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;//父親節(jié)點(diǎn)pair<K, V> _kv;//構(gòu)造函數(shù)AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}int _bf;//平衡因子
};

AVL樹的定義：

template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:private:Node* _root=nullptr;
};

二.AVL樹的插入

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

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

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.second){//當(dāng)前值小于要插入的值，往右邊走parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.second){//當(dāng)前值大于要插入的值，往左邊走parent = cur;cur = cur->_left;}else{//有相同的值了，退出插入return false;}}//當(dāng)cur走到了nullptr，就是找到了要插入的點(diǎn)了cur = new Node(kv);//判斷插入在左邊還是右邊if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//確定父子關(guān)系//…………//更新插入后的平衡因子//…………
}

三.插入后更新平衡因子

新節(jié)點(diǎn)插入后，AVL樹的平衡性可能會(huì)遭到破壞，此時(shí)就需要更新平衡因子，并檢測是否破壞了AVL樹的平衡性

更新平衡因子的規(guī)則：

1. 新增在右邊，則會(huì)讓父平衡因子++，新增在左邊，父平衡因子--
2. 更新后，如果 parent->bf == 0，說明 parent 插入前的平衡因子是 1 or -1，插入填上了矮的一邊，parent 的子樹高度不變，不需要繼續(xù)往上更新。
3. 更新后，如果parent->bf為 1 或 -1， 說明parent插入前的平衡因子是0，說明左右子樹高度相等，插入后有一邊高，parnet 高度變了，需要繼續(xù)往上更新。
4. 更新后，如果 parent->bf == 2 或-2，說明parent插入前的平衡因子是 1 or -1，已經(jīng)到達(dá)平衡臨界值，parent 子樹進(jìn)行旋轉(zhuǎn)處理將樹保持平衡。
5. 更新后，如果 parent->bf >2 或 <-2 ，則說明插入前樹已經(jīng)失去的平衡，要進(jìn)行代碼的檢查。

while (parent)
{//更新平衡因子if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){//沒有新增高度break;}else if(abs(parent->_bf)==1){//平衡因子為1，往上面繼續(xù)找parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 2){//需要旋轉(zhuǎn)了}
}

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

1.左單旋

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

1. 將subR作為一個(gè)根節(jié)點(diǎn)
2. 將subRL作為parent的右節(jié)點(diǎn)(如果subRL存在的話)
3. parent作為subR的左節(jié)點(diǎn)。

左旋的條件是

parent->_bf==2&&cur->_bf==1

旋轉(zhuǎn)之后parent的平衡因子為0，subL的平衡因子也是0。

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

2.右單旋

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

1. 將subL作為一個(gè)根節(jié)點(diǎn)
2. 將subLR作為parent的左節(jié)點(diǎn)(如果subLR存在的話)
3. parent作為subL的右子節(jié)點(diǎn)。

右旋的條件是

parent->_bf==-2&&cur->_bf==-1

旋轉(zhuǎn)之后parent的平衡因子為0，subL的平衡因子也是0。

3.先左單旋再右單旋

新節(jié)點(diǎn)插入較高左子樹的右側(cè)—左右：先左單旋再右單旋
如果將節(jié)點(diǎn)插入到c當(dāng)中，平衡因子就會(huì)發(fā)生改變，所以這里的平衡因子需要分情況討論。
這里通過subLR的平衡因子來確定是在左邊插入還是在右邊插入。
兩種情況下subLR都是0。

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL-> _right;int bf = subLR->_bf;//提前存好，旋轉(zhuǎn)后會(huì)subLR會(huì)發(fā)生改變RotateL(parent->_left);RotateR(parent);subLR->_bf = 0;if (bf == 1){//在右邊插入parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if (bf == 0){//已經(jīng)平衡了parent->_bf = 0;subL->_bf = 0;}else{//插入存在問題assert(false);}
}

4.先右單旋再左單旋

新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左：先右單旋再左單旋
C增加節(jié)點(diǎn)之后高度和d一樣都是h，將其全部旋轉(zhuǎn)到右邊去，然后再通過左旋把30壓下去，將60作為根節(jié)點(diǎn)。
與左右單旋一樣，插入的b還是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);}
}

五.AVL樹的性能分析

AVL樹是一棵絕對(duì)平衡的二叉搜索樹，其要求每個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值都不超過1，這
樣可以保證查詢時(shí)高效的時(shí)間復(fù)雜度，即$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)的(即不會(huì)改變)，可以考慮AVL樹，但一個(gè)結(jié)構(gòu)經(jīng)常修改，就不太適合。

六.檢查是否滿足AVL樹

通過計(jì)算左右子樹的高度差來確定是否滿足AVL樹，因?yàn)槠胶庖蜃邮亲约涸O(shè)置的，如果還通過平衡因子來確定的話會(huì)不太準(zhǔn)。

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;int left = Height(root->_left);int right = Height(root->_right);return max(left, right) + 1;
}

七.源碼

namespace dianxia
{//樹的節(jié)點(diǎn)template<class K, class V>struct AVLTreeNode{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf; // 平衡因子AVLTreeNode(const pair<K, V>& kv):_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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 1 || parent->_bf == -1){// 繼續(xù)更新祖先parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 0){break;}else if (parent->_bf == 2 || parent->_bf == -2){// 需要旋轉(zhuǎn)處理 -- 1、讓這顆子樹平衡 2、降低這顆子樹的高度					//左單旋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;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}private:int _Height(Node* root){if (root == NULL)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}bool _IsBalance(Node* root){if (root == NULL){return true;}int leftH = _Height(root->_left);int rightH = _Height(root->_right);if (rightH - leftH != root->_bf){cout << root->_kv.first << "節(jié)點(diǎn)平衡因子異常" << endl;return false;}return abs(leftH - rightH) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppnode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = subR->_bf = 0;}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 (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 RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;}else{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 == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else{assert(false);}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}

---

本文到此結(jié)束，碼文不易，還請多多支持哦！！！