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