C++實(shí)現(xiàn)AVL樹(shù)的示例詳解
AVL 樹(shù)的概念
也許因?yàn)椴迦氲闹挡粔螂S機(jī),也許因?yàn)榻?jīng)過(guò)某些插入或刪除操作,二叉搜索樹(shù)可能會(huì)失去平衡,甚至可能退化為單鏈表,造成搜索效率低。
AVL Tree 是一個(gè)「加上了額外平衡條件」的二叉搜索樹(shù),其平衡條件的建立是為了確保整棵樹(shù)的深度為 O(log2N)。
AVL Tree 要求任何節(jié)點(diǎn)的左右子樹(shù)高度相差最多為 1。當(dāng)違反該規(guī)定時(shí),就需要進(jìn)行旋轉(zhuǎn)來(lái)保證該規(guī)定。
AVL 樹(shù)的實(shí)現(xiàn)
節(jié)點(diǎn)的定義
AVL 樹(shù)節(jié)點(diǎn)的定義比一般的二叉搜索樹(shù)復(fù)雜,它需要額外一個(gè) parent 指針,方便后續(xù)旋轉(zhuǎn)。并在每個(gè)節(jié)點(diǎn)中引入平衡因子,便于判斷是否需要旋轉(zhuǎn)。
/// @brief AVL 樹(shù)節(jié)點(diǎn)結(jié)構(gòu) /// @tparam K 節(jié)點(diǎn)的 key 值 /// @tparam V 節(jié)點(diǎn)的 value 值 template <class K, class V> struct AVLTreeNode { AVLTreeNode(const pair<K, V>& kv) : _kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) , _bf(0) {} pair<K, V> _kv; AVLTreeNode<K, V>* _parent; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; // 左右子樹(shù)高度相同平衡因子為:0 // 左子樹(shù)高平衡因子為負(fù) // 右子樹(shù)高平衡因子為正 int _bf; };
接口總覽
template<class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: Node* Find(const K& key); bool Insert(const pair<K, V>& kv); private: void RotateR(Node* parent); void RotateL(Node* parent); void RotateLR(Node* parent); void RotateRL(Node* parent); private: Node* _root = nullptr; };
查找
AVL 樹(shù)的查找和普通的搜索二叉樹(shù)一樣:
- 若 key 值大于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中查找
- 若 key 值小于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中查找
- 若 key 值等于當(dāng)前節(jié)點(diǎn)的值,返回當(dāng)前節(jié)點(diǎn)的地址
- 若找到空,查找失敗,返回空指針
/// @brief 查找指定 key 值 /// @param key 要查找的 key /// @return 找到返回節(jié)點(diǎn)的指針,沒(méi)找到返回空指針 Node* Find(const K& key) { Node* cur = _root; while (cur != nullptr) { // key 值與當(dāng)前節(jié)點(diǎn)值比較 if (key > cur->_kv.first) { cur = cur->_right; } else if (key < cur->_kv.first) { cur = cur->_left; } else { return cur; } } return nullptr; }
插入
AVL 的插入整體分為兩步:
- 按照二叉搜索樹(shù)的方式將節(jié)點(diǎn)插入
- 調(diào)整節(jié)點(diǎn)的平衡因子
平衡因子是怎么調(diào)整的?
設(shè)新插入的節(jié)點(diǎn)為 pCur,新插入節(jié)點(diǎn)的父節(jié)點(diǎn)為 pParent。在插入之前,pParent 的平衡因子有三種可能:0、-1、1。
插入分為兩種:
- pCur 插入到 pParent 的左側(cè),將 pParent 的平衡因子減 1
- pCur 插入到 pParent 的右側(cè),將 pParent 的平衡因子加 1
此時(shí),pParent 的平衡因子可能有三種情況:0、正負(fù) 1、正負(fù) 2。
- 0:說(shuō)明插入之前是正負(fù) 1,插入后被調(diào)整為 0,滿足 AVL 性質(zhì)插入成功
- 正負(fù) 1:說(shuō)明插入之前是 0,插入后被調(diào)整為正負(fù) 1,此時(shí) pParent 變高,需要繼續(xù)向上更新
- 正負(fù) 2:說(shuō)明插入之前是正負(fù) 1,插入后被調(diào)整為正負(fù) 2,此時(shí)破壞了規(guī)定,需要旋轉(zhuǎn)處理
/// @brief 插入指定節(jié)點(diǎn) /// @param kv 待插入的節(jié)點(diǎn) /// @return 插入成功返回 true,失敗返回 false bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); return true; } // 先找到要插入的位置 Node* parent = nullptr; Node* cur = _root; while (cur != nullptr) { if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { // 已經(jīng)存在,插入失敗 return false; } } // 將節(jié)點(diǎn)插入 cur = new Node(kv); if (kv.first > parent->_kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } // 更新平衡因子,直到正常 while (parent != nullptr) { // 調(diào)整父親的平衡因子 if (parent->_left == cur) { --parent->_bf; } else { ++parent->_bf; } if (parent->_bf == 0) { // 此時(shí)不需要再繼續(xù)調(diào)整了,直接退出 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 此時(shí)需要繼續(xù)向上調(diào)整 cur = parent; parent = parent->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 此時(shí)需要旋轉(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); } // 旋轉(zhuǎn)完了就平衡了,直接退出 break; } else { // 此時(shí)說(shuō)明之前就處理錯(cuò)了 assert(false); } // end of if (parent->_bf == 0) } // end of while (parent != nullptr) return true; }
旋轉(zhuǎn)
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 X,由于節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn),因此可以分為四種情況:
- 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的左子樹(shù)——左左:右單旋
- 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的右子樹(shù)——左右:左右雙旋
- 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的右子樹(shù)——右右:左單旋
- 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的左子樹(shù)——右左:右左雙旋
右單旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的左子樹(shù)為 subL,subL 的右子樹(shù)為 subLR。
右單旋的操作流程:
- 讓 subLR 作為 parent 的左子樹(shù)
- 讓 parent 作為 subL 的右子樹(shù)
- 讓 subL 作為整個(gè)子樹(shù)的新根
- 更新平衡因子
/// @brief 進(jìn)行右單旋 /// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn) void RotateR(Node* parent) { Node* pParent = parent->_parent; Node* subL = parent->_left; Node* subLR = parent->_left->_right; // 更改鏈接關(guān)系 // 1. subLR 作為 parent 的左子樹(shù) parent->_left = subLR; if (subLR != nullptr) { subLR->_parent = parent; } // 2. parent 作為 subL 的右子樹(shù) subL->_right = parent; parent->_parent = subL; // 3. subL 作為整個(gè)子樹(shù)的新根 if (parent == _root) { // parent 為 _root,此時(shí)令 subL 為 _root _root = subL; subL->_parent = nullptr; } else { // parent 不為 _root,pParent 也就不為空 if (parent == pParent->_left) { pParent->_left = subL; } else { pParent->_right = subL; } subL->_parent = pParent; } // 4. 更新平衡因子 // 觀察上圖明顯可知 subL->_bf = 0; parent->_bf = 0; }
左單旋
左單旋與右單旋類似,只是方向不同。
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的右子樹(shù)為 subR,subR 的左子樹(shù)為 subRL。
左單旋的操作流程:
- 讓 subRL 作為 parent 的右子樹(shù)
- 讓 parent 作為 subR 的左子樹(shù)
- 讓 subR 作為整個(gè)子樹(shù)的新根
- 更新平衡因子
/// @brief 進(jìn)行左單旋 /// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn) void RotateL(Node* parent) { Node* pParetn = parent->_parent; Node* subR = parent->_right; Node* subRL = parent->_right->_left; // 更改鏈接關(guān)系 // 1. subRL 作為 parent 的右子樹(shù) parent->_right = subRL; if (subRL != nullptr) { subRL->_parent = parent; } // 2. parent 作為 subR 的左子樹(shù) subR->_left = parent; parent->_parent = subR; // 3. subR 作為整個(gè)子樹(shù)的新根 if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (parent == pParetn->_left) { pParetn->_left = subR; } else { pParetn->_right = subR; } subR->_parent = pParetn; } // 4. 更新平衡因子 subR->_bf = 0; parent->_bf = 0; }
左右雙旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的左子樹(shù)為 subL,subL 的右子樹(shù)為 subLR。
左右雙旋就是對(duì) subL 進(jìn)行一次左單旋,對(duì) parent 進(jìn)行一次右單旋。雙旋也就完成了,要注意的是雙旋后平衡因子的更新。
此時(shí)分三種情況:
1.新插入的節(jié)點(diǎn)是 subLR 的右子樹(shù)
2.新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù)
3.新插入的是 subLR
結(jié)合上述情況,寫出如下代碼:
/// @brief 進(jìn)行左右雙旋 /// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn) void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = parent->_left->_right; int bf = subLR->_bf; RotateL(subL); RotateR(parent); if (bf == 1) { // 新插入節(jié)點(diǎn)是 subLR 的右子樹(shù) parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { // 新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù) parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 0) { // 新插入的節(jié)點(diǎn)是 subLR parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
右左雙旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的右子樹(shù)為 subR,subR 的左子樹(shù)為 subRL。
右左雙旋就是對(duì) subR 進(jìn)行一次右單旋,對(duì) parent 進(jìn)行一次左單旋。流程和左右雙旋一樣,這里就不過(guò)多介紹了。
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = parent->_right->_left; int bf = subRL->_bf; RotateR(subR); RotateL(parent); if (bf == 1) { // 新插入節(jié)點(diǎn)是 subRL 的右子樹(shù) parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { // 新插入的節(jié)點(diǎn)是 subRL 的左子樹(shù) parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 0) { // 新插入的節(jié)點(diǎn)是 subRL parent->_bf = 0; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } }
以上就是C++實(shí)現(xiàn)AVL樹(shù)的示例詳解的詳細(xì)內(nèi)容,更多關(guān)于C++ AVL樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
c++下使用windows api遍歷指定文件夾及其子文件夾中的文件
這篇文章主要介紹了c++下使用windows api遍歷指定文件夾及其子文件夾中的文件實(shí)現(xiàn)代碼,一般都是通過(guò)c++自帶的函數(shù)實(shí)現(xiàn)2021-07-07???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法
這篇文章主要介紹了???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法,文章圍繞主題展開(kāi)詳細(xì)介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-05-05一步步從底層入手搞定C++引用與內(nèi)聯(lián)函數(shù)
內(nèi)聯(lián)函數(shù)是代碼插入到調(diào)用者代碼處的函數(shù),內(nèi)聯(lián)函數(shù)通過(guò)避免被調(diào)用的開(kāi)銷來(lái)提高執(zhí)行效率,下面這篇文章主要給大家介紹了關(guān)于如何從底層入手搞定C++引用與內(nèi)聯(lián)函數(shù)的相關(guān)資料,需要的朋友可以參考下2023-03-03C++設(shè)計(jì)模式之策略模式(Strategy)
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計(jì)模式之策略模式Strategy ,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-04-04C++實(shí)現(xiàn)獲取IP、子網(wǎng)掩碼、網(wǎng)關(guān)、DNS等本機(jī)網(wǎng)絡(luò)參數(shù)的方法
這篇文章主要介紹了C++實(shí)現(xiàn)獲取IP、子網(wǎng)掩碼、網(wǎng)關(guān)、DNS等本機(jī)網(wǎng)絡(luò)參數(shù)的方法,需要的朋友可以參考下2014-07-07C++線程安全容器stack和queue的使用詳細(xì)介紹
stack是一種容器適配器,專門用在具有后進(jìn)先出操作的上下文環(huán)境中,其刪除只能從容器的一端進(jìn)行 元素的插入與提取操作;隊(duì)列是一種容器適配器,專門用于在FIFO上下文(先進(jìn)先出)中操作,其中從容器一端插入元素,另一端提取元素2022-08-08C語(yǔ)言中關(guān)于sizeof 和 strlen的區(qū)別分析
本文通過(guò)示例簡(jiǎn)單分析了4種情況下C語(yǔ)言中sizeof 和 strlen的區(qū)別,算是個(gè)人經(jīng)驗(yàn)的一個(gè)小小的總結(jié),如有遺漏還請(qǐng)大家告知。2015-02-02C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04