當(dāng)下網(wǎng)站建設(shè)企業(yè)網(wǎng)站模板 免費(fèi)
文章目錄
- 前言
- 一、AVL 樹介紹
- 二、AVL樹節(jié)點(diǎn)的定義
- 三、AVL樹的插入
- 四、AVL樹的旋轉(zhuǎn)
- 五、AVL樹的驗(yàn)證
- 六、AVL樹的刪除
- 七、AVL樹的性能
- 八、AVL樹的實(shí)現(xiàn)
前言
??在前面的文章中介紹了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(log2N)O(log_2 N)O(log2?N),搜索時(shí)間復(fù)雜度O(log2N)O(log_2 N)O(log2?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樹的插入過程可以分為兩步:
- 先按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到AVL樹中
- 新節(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,分以下情況考慮:
- Parent的平衡因子為2,說明Parent的右子樹高,設(shè)Parent的右子樹的根為SubR。當(dāng)SubR的平衡因子為1時(shí),執(zhí)行左單旋。當(dāng)SubR的平衡因子為-1時(shí),執(zhí)行右左雙旋。
- 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)的意義
- 平衡
- 降高度
五、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(log2N)O(log_2 N)O(log2?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;
}