C++中AVL樹(shù)的底層以及實(shí)現(xiàn)方法總結(jié)
一、AVL樹(shù)的概念
AVL樹(shù)是一種高度平衡的平衡二叉樹(shù),相比于搜索二叉樹(shù),它的特點(diǎn)在于左右子樹(shù)都為AVL樹(shù)且樹(shù)的高度差的絕對(duì)值不超過(guò)1。這里我們會(huì)引入一個(gè)新的概念叫做平衡因子。平衡因子也就是左右子樹(shù)的高度差,我們可以通過(guò)平衡因子方便我們后續(xù)去觀察和控制樹(shù)是否平衡。
二、AVL樹(shù)的性質(zhì)
AVL樹(shù)主要有三大性質(zhì):
1.每棵樹(shù)的左右子樹(shù)都是AVL樹(shù)。
2.左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。
3.每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)平衡因子,且任何一個(gè)節(jié)點(diǎn)的平衡因子都為1、0、-1。
三、AVL樹(shù)的實(shí)現(xiàn)
1. 樹(shù)的基本結(jié)構(gòu)
AVL樹(shù)的結(jié)點(diǎn)包含了左右節(jié)點(diǎn)的指針以及父親節(jié)點(diǎn)的指針,同時(shí)還有有key、value以及代表樹(shù)平衡的平衡因子。
template<class K, class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; //平衡因子 int _bf; AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };
2. 樹(shù)的插入
樹(shù)的插入按照搜索二叉樹(shù)的規(guī)則進(jìn)行插入。插入節(jié)點(diǎn)后更新平衡因子,如果沒(méi)有違反規(guī)則(即沒(méi)有導(dǎo)致節(jié)點(diǎn)的平衡因子變成2/-2),則插入結(jié)束;如果違反規(guī)則,則樹(shù)會(huì)不平衡,需要進(jìn)行旋轉(zhuǎn)操作。
平衡因子的更新規(guī)則:
1.平衡因子 = 右子樹(shù)高度 - 左子樹(shù)高度。
2.只有子樹(shù)高度的變化才會(huì)影響當(dāng)前節(jié)點(diǎn)的平衡因子。
3.插入節(jié)點(diǎn)后會(huì)增加數(shù)的高度,若新增節(jié)點(diǎn)在parent的右子樹(shù),則parent的平衡因子++,相反在parent的左子樹(shù)時(shí),則平衡因子- -。
每更新完一個(gè)節(jié)點(diǎn)的平衡因子都需要進(jìn)行以下判斷:
1.如果parent的平衡因子等于1/-1時(shí),說(shuō)明parent原先的平衡因子為0,插入節(jié)點(diǎn)后左子樹(shù)或右子樹(shù)的高度增加了,說(shuō)明還需要向上更新平衡因子。
2.如果parent的平衡因子等于0,說(shuō)明parent原先的平衡因子為1/-1,插入節(jié)點(diǎn)后左右兩棵子樹(shù)從不平衡變平衡了,說(shuō)明無(wú)需更新平衡因子。
3.如果parent的平衡因子等于2/-2時(shí),說(shuō)明parent原先的平衡因子等于1/-1,插入節(jié)點(diǎn)后插入到了較高的那一棵子樹(shù),說(shuō)明此時(shí)以parent為根節(jié)點(diǎn)的子樹(shù)已經(jīng)不平衡了,需要進(jìn)行旋轉(zhuǎn)處理。
bool Insert(const pair<K, V>& kv) { //如果樹(shù)為空,則插入的節(jié)點(diǎn)就是根節(jié)點(diǎn) 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ù)往上進(jìn)行更新 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //不平衡,旋轉(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); } else { assert(false); } } else { assert(false); } break; } return true; }
3. 樹(shù)的旋轉(zhuǎn)
旋轉(zhuǎn)的目的就是讓樹(shù)從失衡到平衡,降低樹(shù)的高度。旋轉(zhuǎn)主要分為四種,分別為左單旋、右單旋、左右雙旋和右左雙旋。下面我們具體講講每一種旋轉(zhuǎn)的內(nèi)部邏輯。
• 左單旋
條件:新節(jié)點(diǎn)插入到子樹(shù)較高的右側(cè)。
我們用圖來(lái)感受一下其旋轉(zhuǎn)的過(guò)程:
1.先將15的左子樹(shù)的節(jié)點(diǎn)12變成10的右子樹(shù)。
2.再將10變成15的左子樹(shù),15成為新樹(shù)的根節(jié)點(diǎn)。
3.更新平衡因子
由于左單旋的情況很多,我們也可以用一張抽象圖來(lái)表示:
代碼所示:
//左單旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subR; if (subRL) subRL->_parent = parent; Node* pparent = parent->_parent; if (pparent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (pparent == parent->_right) { parent->_right = subR; } else { parent->_left = subR; } subR->_parent = pparent; } parent->_bf = subR->_bf = 0; }
• 右單旋
條件:新節(jié)點(diǎn)插入到子樹(shù)較高的左側(cè)
用圖來(lái)感受旋轉(zhuǎn)的過(guò)程:
我們會(huì)發(fā)現(xiàn)和左單旋和相似
1.先將5的右子樹(shù)的值b變成10的左子樹(shù)。
2.再將10變成5的右子樹(shù),旋轉(zhuǎn)完后5成為整棵樹(shù)的根節(jié)點(diǎn)。
3.更新平衡因子。
代碼所示:
//右單旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if(subLR) subLR->_parent = parent; Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (pparent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (pparent == parent->_left) { parent->_left = subL; } else { parent->_right = subL; } subL->_parent = pparent; } parent->_bf = subL->_bf = 0; }
• 左右雙旋
條件:新節(jié)點(diǎn)插入到較高左子樹(shù)的右側(cè)。
下面我們用圖來(lái)演示一下其旋轉(zhuǎn)過(guò)程:
1.插入新節(jié)點(diǎn)
2.以節(jié)點(diǎn)5為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
3.以節(jié)點(diǎn)為10進(jìn)行右單旋
4.旋轉(zhuǎn)完后更新平衡因子。
平衡因子又分為三種情況:
1.當(dāng)subLR的平衡因子為-1時(shí),左右雙旋后parent、subL,subLR的平衡因子分別為1、0、0。
2.當(dāng)subLR的平衡因子為1時(shí),左右雙旋后parent、subL,subLR的平衡因子分別為0、-1、0。
3.當(dāng)subLR的平衡因子為0時(shí),左右雙旋后parent、subL,subLR的平衡因子分別為0、0、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) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
• 右左雙旋
條件:插入到較高右子樹(shù)的左側(cè)
其旋轉(zhuǎn)過(guò)程和左右雙旋類(lèi)似,這就不一一列舉了。
旋轉(zhuǎn)完過(guò)后也是需要更新平衡因子,平衡因子也是跟左右雙旋一樣有三種情況。
代碼所示:
//右左雙旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent); RotateL(parent); if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
四、AVL樹(shù)的其它功能
1. 樹(shù)的查找
定義一個(gè)cur指針從樹(shù)的根節(jié)點(diǎn)開(kāi)始查找,按一下規(guī)則進(jìn)行查找:
1.當(dāng)key的值小于當(dāng)前節(jié)點(diǎn)的值時(shí),則在該節(jié)點(diǎn)的左邊進(jìn)行查找。
2.當(dāng)key的值大于當(dāng)前節(jié)點(diǎn)的值時(shí),則在該節(jié)點(diǎn)的右邊進(jìn)行查找。
3.若key的值等于當(dāng)前節(jié)點(diǎn)的值時(shí),則說(shuō)明查找成功,返回true。
4.若遍歷完還沒(méi)查找到該節(jié)點(diǎn)的值,則說(shuō)明沒(méi)有此節(jié)點(diǎn),返回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; }
2. 樹(shù)的遍歷
我們遍歷方式有前序、中序、后序、層序等方式,我們?cè)谶@就采用中序遍歷的方式來(lái)遍歷樹(shù)的每一節(jié)點(diǎn)。
代碼所示:
void _Inorder(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _Inorder(root->_right); }
3. 樹(shù)的高度
int _Height(Node* root) { if (root == nullptr) { return; } int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }
4. 樹(shù)的大小
返回左子樹(shù)+右子樹(shù)再加上根節(jié)點(diǎn)即可。
int _Size(Node* root) { if (root == nullptr) { return; } return _Size(root->_left) + _Size(root->_right) + 1; }
五、總結(jié)
1. AVL樹(shù)的優(yōu)缺點(diǎn)
優(yōu)點(diǎn):
**1.查找效率高:**由于AVL樹(shù)總是保持平衡,其高度相對(duì)較低,因此查找操作的時(shí)間復(fù)雜度為O(log2N),效率較高。
2.結(jié)構(gòu)穩(wěn)定: AVL樹(shù)的平衡性使得其結(jié)構(gòu)相對(duì)穩(wěn)定,不會(huì)出現(xiàn)極端不平衡的情況,從而保證了操作的穩(wěn)定性和可靠性。
缺點(diǎn):
1.插入和刪除復(fù)雜: AVL樹(shù)在插入和刪除節(jié)點(diǎn)時(shí),可能需要通過(guò)旋轉(zhuǎn)操作來(lái)保持樹(shù)的平衡,比較復(fù)雜。
2.可能導(dǎo)致性能下降: 在頻繁插入和刪除的場(chǎng)景下,AVL樹(shù)需要不斷地進(jìn)行旋轉(zhuǎn)操作來(lái)保持平衡,這就有可能導(dǎo)致性能降低。
2. 完整代碼
#include<iostream> #include<assert.h> using namespace std; template<class K, class V> struct AVLTreeNode { // 需要parent指針,后續(xù)更新平衡因子可以看到 pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; //平衡因子 int _bf; // balance factor AVLTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _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ù)往上進(jìn)行更新 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { //不平衡,旋轉(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); } else { assert(false); } } else { assert(false); } break; } return true; } //右單旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if(subLR) subLR->_parent = parent; Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL; if (pparent == nullptr) { _root = subL; subL->_parent = nullptr; } else { if (pparent == parent->_left) { parent->_left = subL; } else { parent->_right = subL; } subL->_parent = pparent; } parent->_bf = subL->_bf = 0; } //左單旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subR; if (subRL) subRL->_parent = parent; Node* pparent = parent->_parent; if (pparent == nullptr) { _root = subR; subR->_parent = nullptr; } else { if (pparent == parent->_right) { parent->_right = subR; } else { parent->_left = subR; } subR->_parent = pparent; } parent->_bf = subR->_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) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subLR->_bf = 0; subL->_bf = -1; parent->_bf = 0; } else if (bf == 0) { subLR->_bf = 0; subL->_bf = 0; parent->_bf = 0; } else { assert(false); } } //右左雙旋 void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent); RotateL(parent); if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } } void Inorder() { _Inorder(_root); cout << endl; } void Hight() { return _Hight(_root); } void Size() { return _Size(_root); } private: void _Inorder(Node* root) { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _Inorder(root->_right); } int _Height(Node* root) { if (root == nullptr) { return; } int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } int _Size(Node* root) { if (root == nullptr) { return; } return _Size(root->_left) + _Size(root->_right) + 1; } 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; } private: Node* _root = nullptr; };
總結(jié)
到此這篇關(guān)于C++中AVL樹(shù)的底層以及實(shí)現(xiàn)方法總結(jié)的文章就介紹到這了,更多相關(guān)C++ AVL樹(shù)底層及實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++應(yīng)用Eigen庫(kù)對(duì)應(yīng)實(shí)現(xiàn)matlab中部分函數(shù)問(wèn)題
這篇文章主要介紹了C++應(yīng)用Eigen庫(kù)對(duì)應(yīng)實(shí)現(xiàn)matlab中部分函數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-12-12C++實(shí)現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08淺談C語(yǔ)言中的sizeof()和strlen()的區(qū)別
本文主要介紹了C語(yǔ)言中的sizeof()和strlen()的區(qū)別,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05