您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++如何實現(xiàn)AVL樹”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
也許因為插入的值不夠隨機(jī),也許因為經(jīng)過某些插入或刪除操作,二叉搜索樹可能會失去平衡,甚至可能退化為單鏈表,造成搜索效率低。
AVL Tree 是一個「加上了額外平衡條件」的二叉搜索樹,其平衡條件的建立是為了確保整棵樹的深度為 O(log2N)。
AVL Tree 要求任何節(jié)點(diǎn)的左右子樹高度相差最多為 1。當(dāng)違反該規(guī)定時,就需要進(jìn)行旋轉(zhuǎn)來保證該規(guī)定。
AVL 樹節(jié)點(diǎn)的定義比一般的二叉搜索樹復(fù)雜,它需要額外一個 parent 指針,方便后續(xù)旋轉(zhuǎn)。并在每個節(jié)點(diǎn)中引入平衡因子,便于判斷是否需要旋轉(zhuǎn)。
/// @brief AVL 樹節(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; // 左右子樹高度相同平衡因子為:0 // 左子樹高平衡因子為負(fù) // 右子樹高平衡因子為正 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 值大于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的右子樹中查找
若 key 值小于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的左子樹中查找
若 key 值等于當(dāng)前節(jié)點(diǎn)的值,返回當(dāng)前節(jié)點(diǎn)的地址
若找到空,查找失敗,返回空指針
/// @brief 查找指定 key 值 /// @param key 要查找的 key /// @return 找到返回節(jié)點(diǎn)的指針,沒找到返回空指針 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 的插入整體分為兩步:
按照二叉搜索樹的方式將節(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
此時,pParent 的平衡因子可能有三種情況:0、正負(fù) 1、正負(fù) 2。
0:說明插入之前是正負(fù) 1,插入后被調(diào)整為 0,滿足 AVL 性質(zhì)插入成功
正負(fù) 1:說明插入之前是 0,插入后被調(diào)整為正負(fù) 1,此時 pParent 變高,需要繼續(xù)向上更新
正負(fù) 2:說明插入之前是正負(fù) 1,插入后被調(diào)整為正負(fù) 2,此時破壞了規(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) { // 此時不需要再繼續(xù)調(diào)整了,直接退出 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 此時需要繼續(xù)向上調(diào)整 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); } // 旋轉(zhuǎn)完了就平衡了,直接退出 break; } else { // 此時說明之前就處理錯了 assert(false); } // end of if (parent->_bf == 0) } // end of while (parent != nullptr) return true; }
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 X,由于節(jié)點(diǎn)最多擁有兩個子節(jié)點(diǎn),因此可以分為四種情況:
插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的左子樹——左左:右單旋
插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的右子樹——左右:左右雙旋
插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的右子樹——右右:左單旋
插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的左子樹——右左:右左雙旋
右單旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的左子樹為 subL,subL 的右子樹為 subLR。
右單旋的操作流程:
讓 subLR 作為 parent 的左子樹
讓 parent 作為 subL 的右子樹
讓 subL 作為整個子樹的新根
更新平衡因子
/// @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 的左子樹 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; }
左單旋
左單旋與右單旋類似,只是方向不同。
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的右子樹為 subR,subR 的左子樹為 subRL。
左單旋的操作流程:
讓 subRL 作為 parent 的右子樹
讓 parent 作為 subR 的左子樹
讓 subR 作為整個子樹的新根
更新平衡因子
/// @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 的右子樹 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; }
左右雙旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的左子樹為 subL,subL 的右子樹為 subLR。
左右雙旋就是對 subL 進(jìn)行一次左單旋,對 parent 進(jìn)行一次右單旋。雙旋也就完成了,要注意的是雙旋后平衡因子的更新。
此時分三種情況:
1.新插入的節(jié)點(diǎn)是 subLR 的右子樹
2.新插入的節(jié)點(diǎn)是 subLR 的左子樹
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 的右子樹 parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if (bf == -1) { // 新插入的節(jié)點(diǎn)是 subLR 的左子樹 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 的右子樹為 subR,subR 的左子樹為 subRL。
右左雙旋就是對 subR 進(jìn)行一次右單旋,對 parent 進(jìn)行一次左單旋。流程和左右雙旋一樣,這里就不過多介紹了。
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 的右子樹 parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else if (bf == -1) { // 新插入的節(jié)點(diǎn)是 subRL 的左子樹 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++如何實現(xiàn)AVL樹”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。