高階數(shù)據(jù)結(jié)構(gòu)	相關(guān)知識(shí)點(diǎn)	可以通過(guò)點(diǎn)擊	以下鏈接進(jìn)行學(xué)習(xí)	一起加油！
二叉搜索樹

大家好，這里是店小二！今天我們將深入探討高階數(shù)據(jù)結(jié)構(gòu)中的AVL樹。AVL樹是一種自平衡的二叉搜索樹，可以看作是對(duì)傳統(tǒng)二叉搜索樹的優(yōu)化版本。如果你對(duì)數(shù)據(jù)結(jié)構(gòu)感興趣，快拿出你的小本本，和我們一起開始這段探索之旅吧！

🌈個(gè)人主頁(yè)：是店小二呀
🌈C語(yǔ)言專欄：C語(yǔ)言
🌈C++專欄： C++
🌈初階數(shù)據(jù)結(jié)構(gòu)專欄： 初階數(shù)據(jù)結(jié)構(gòu)
🌈高階數(shù)據(jù)結(jié)構(gòu)專欄： 高階數(shù)據(jù)結(jié)構(gòu)
🌈Linux專欄： Linux

🌈喜歡的詩(shī)句:無(wú)人扶我青云志 我自踏雪至山巔

前文

關(guān)于上篇二叉搜索樹性能那塊，探討了二叉搜索樹雖然可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。

因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了一種解決上述問(wèn)題的方法：當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹高度之差的絕對(duì)值不超過(guò)1(需要對(duì)樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長(zhǎng)度，按照這種規(guī)則形成的二叉搜索樹為AVL樹，保持著嚴(yán)格的平衡。

一、AVL樹概念

一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：

• 它的左右子樹都是AVL樹
• 左右子樹高度之差(簡(jiǎn)稱平衡因子)的絕對(duì)值不超過(guò)1(-1/0/1)
• 平衡因子并不是必須，只是他的一種實(shí)現(xiàn)方式

如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個(gè)結(jié)點(diǎn)，其高度可保持在logn,搜索時(shí)間復(fù)雜度O(logn)

平衡因子計(jì)算:

• 平衡因子 = 右子樹高度 - 左子樹高度

二、AVL樹實(shí)現(xiàn)

2.1 AVL樹節(jié)點(diǎn)的定義 (成員默認(rèn)訪問(wèn)公有)

template<class K, class V>struct AVLTreeNode{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;//主要類型AVLTreeNode(const pair<K, V> & kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}};

AVL樹每個(gè)結(jié)構(gòu)存儲(chǔ)一個(gè)pair<K, V>對(duì)象，其中需要parent指針目的是為了方便訪問(wèn)當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)。

考慮到AVLTreeNode<K ,V>書寫麻煩，使用typedef進(jìn)行類型重定義typedef AVLTreeNode<K, V> Node;

2.2 AVL樹查找邏輯

	Node* Find(const K& key){//按照搜索樹Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{//返回當(dāng)前節(jié)點(diǎn)的指針return cur;}}//防止意外發(fā)生。return nullptr;}

本質(zhì)上來(lái)說(shuō)AVL樹屬于二叉搜索樹，關(guān)于cur->_kv.first是cur通過(guò)指針去訪問(wèn)Node類中類型為pair<K, V>對(duì)象的_kv。通過(guò)set與map簡(jiǎn)單學(xué)習(xí)。可以得知pair內(nèi)部實(shí)現(xiàn)邏輯，_這里的kv.first中first是K類型的對(duì)象。同時(shí)AVL也是二叉樹搜索樹，查找邏輯當(dāng)然是使用二叉搜索樹的邏輯。

2.3 AVL樹插入邏輯

既然AVL也是二叉搜索樹，那么插入邏輯也是一樣的，不同在于需要進(jìn)行平衡因子的調(diào)正。(平衡因子 = 右子樹高度 - 左子樹高度)

當(dāng)插入節(jié)點(diǎn)結(jié)束后，對(duì)插入節(jié)點(diǎn)的父親節(jié)點(diǎn)進(jìn)行平衡因子的修改。當(dāng)對(duì)于父親節(jié)點(diǎn)達(dá)到特定值會(huì)對(duì)應(yīng)不同的情況，不斷利用parent向上調(diào)整父親節(jié)點(diǎn)的平衡因子。

通過(guò)例圖去分析，當(dāng)父親平衡因子到達(dá)特定值對(duì)應(yīng)不同情況:

第一張:當(dāng)parent平衡因子從1或-1變到0

第二張:這里出現(xiàn)兩種情況，parent平衡因子從0變到1或-1，parent平衡因子從1或-1變到2或-2。只有從0變到1或-1，沒(méi)有從2或-2變成1或-1，因?yàn)楫?dāng)parent平衡因子絕對(duì)值超過(guò)1時(shí)，已經(jīng)出現(xiàn)問(wèn)題，需要進(jìn)行調(diào)正

具體說(shuō)明:

1. 按照搜索樹規(guī)則插入
2. 某個(gè)父親節(jié)點(diǎn)的平衡因子
   • 插入父親的左孩子，父親平衡因子–
   • 插入父親的右孩子，父親平衡因子++

while (parent)
{//規(guī)矩平衡因子的規(guī)則，是根據(jù)特性和下面代碼得來(lái)的if (parent->_left == cur){parent->_bf--;}else if (parent->_right == cur){parent->_bf++;}//判斷是否回到父親節(jié)點(diǎn)改動(dòng)if (parent->_bf == 0){//沒(méi)有啥問(wèn)題，可以跳出程序break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//出現(xiàn)問(wèn)題,這種情況是由情況二變化過(guò)來(lái)的，那么就是說(shuō)，cur和parent向上移動(dòng)了else if (parent->_bf == 2 || parent->_bf == -2{//.............}
}

理解:

在節(jié)點(diǎn)插入后，需要進(jìn)行平衡因子的更新。更新順序是從下到上，結(jié)合著父親節(jié)點(diǎn)平衡因子進(jìn)行判斷是否需要繼續(xù)向上更新。

根據(jù)判斷更新父親的平衡因子狀況進(jìn)行處理(該平衡因子更新完后):

• 父親平衡因子 == 0，父親所在子樹高度不變，不再繼續(xù)往上更新，插入結(jié)束
• 父親平衡因子 == 1 or -1, 父親所在子樹高度變了，繼續(xù)往上更新上面節(jié)點(diǎn)的平衡因子
• 父親平衡因子 == 2 or -2, 父親所在的子樹已經(jīng)不平衡了，需要旋轉(zhuǎn)處理

三、AVL的旋轉(zhuǎn)(重點(diǎn))

如果在一顆原本是平衡的AVL樹中插入一個(gè)新節(jié)點(diǎn)，可能造成不平衡，此時(shí)必須調(diào)整樹的結(jié)構(gòu)使之平衡化。根據(jù)節(jié)點(diǎn)插入位置的不同，AVL樹的旋轉(zhuǎn)分為四種:

這里可以將前面兩種歸為單旋進(jìn)行處理，而后面兩種需要通過(guò)雙旋進(jìn)行處理。

提前說(shuō)明:一個(gè)AVL樹有多個(gè)AVL樹或者說(shuō)一個(gè)復(fù)雜的AVL樹是由許多個(gè)簡(jiǎn)單的AVL樹進(jìn)行組合而成的。那么如果插入一個(gè)節(jié)點(diǎn)導(dǎo)致AVL樹失去平衡，這里AVL樹指以插入節(jié)點(diǎn)的父親節(jié)點(diǎn)為根節(jié)點(diǎn)的子AVL樹。遵守一個(gè)有問(wèn)題解決問(wèn)題，如果只是這一課AVL樹有問(wèn)題，就解決這顆AVL樹，正常的AVL樹我們是不要去過(guò)多的進(jìn)行處理。

根據(jù)說(shuō)明，如果將一整棵AVL樹全部拆分進(jìn)行研究，不同節(jié)點(diǎn)插入的位置很多選擇，情況有很多種，難以全部羅列出來(lái)，而且沒(méi)有必要，如果將一顆有問(wèn)題AVL樹治好，就可以將任何一顆AVL樹治好，所以這邊采用使用抽象圖進(jìn)行分析。

3.1 選用抽象圖探討AVL旋轉(zhuǎn)

其中使用a、b、c子AVL樹及其高度設(shè)置為h

抽象圖中的抽象的AVL樹平衡因子這里不用看的，目前羅列的情況是可以包含這里的，這里小部分就是大部分調(diào)正平衡因子的過(guò)程，意味著這部分也可以是抽象AVL樹中的情況按照當(dāng)前處理已經(jīng)進(jìn)行了調(diào)整。

3.2 單旋問(wèn)題

使用單旋場(chǎng)景:parent->_bf == 2 && cur->_bf == 1或者parent->_bf == -2 && cur->_bf == -1

3.2.1 新節(jié)點(diǎn)插入較高左子樹的左側(cè)–左左:右單旋

場(chǎng)景:parent->_ bf == -2 && cur->_bf == -1

具體解析旋轉(zhuǎn)步驟:

目前AVL樹是平衡的，當(dāng)插入新節(jié)點(diǎn)30到左子樹中，左子樹高度加一層，導(dǎo)致以60為根的子AVL樹失去平衡。為了使得平衡，意味著節(jié)點(diǎn)60的右子樹也需要增加一層，那么將60節(jié)點(diǎn)成為30節(jié)點(diǎn)的左孩子，同時(shí)原本30節(jié)點(diǎn)的左孩子和60節(jié)點(diǎn)成為30節(jié)點(diǎn)的左孩子的高度相同，那么將原本30節(jié)點(diǎn)的左孩子成為60節(jié)點(diǎn)有孩子。這里保證了30節(jié)點(diǎn)原本左孩子一定是小于60節(jié)點(diǎn)的。更新節(jié)點(diǎn)的平衡因子即可，簡(jiǎn)單概況就是30 < b子樹 < 60 < c子樹

旋轉(zhuǎn)過(guò)程中，有以下幾點(diǎn)情況需要考慮:

1. 30節(jié)點(diǎn)的右孩子可能存在，也可能不存在
2. 60可能是根節(jié)點(diǎn)，也可能是子樹
   • 如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，要更新根節(jié)點(diǎn)
   • 如果是子樹，可能是某個(gè)節(jié)點(diǎn)的左子樹，也可能是右子樹

void RotateR(Node* parent)
{Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;if (SubLR)SubLR->_parent = parent;SubL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){SubL = _root;SubL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubL;}else if(ppNode->_right == parent){ppNode->_right = SubL;}SubL->_parant = ppNode;}SubL->_bf = 0;parent->_bf = 0;
}

通過(guò)旋轉(zhuǎn)使得不平衡AVL樹得到調(diào)整，這里不需要考慮向上更新平衡因子。從抽象圖中可以得出旋轉(zhuǎn)后結(jié)論，直接使用結(jié)論修改平衡因子就行。

3.2.2 新節(jié)點(diǎn)插入較高右子樹的右側(cè)–右右:左單旋

場(chǎng)景:parent->_ bf == 2 && cur->_bf == 1

這里和右單旋是差不多的，具體流程可以去看上述和代碼分析

void RotateL(Node* parent)
{Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL)SubR->_parent = parent;SubR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){SubR = _root;SubR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubR;}else if (ppNode->_right == parent){ppNode->_right = SubR;}SubR->_parant = ppNode;}SubR->_bf = 0;parent->_bf = 0;
}

3.3 雙旋解決問(wèn)題

如果出現(xiàn)了這種if (parent->_bf == 2 || cur->_bf == -1), if (parent->_bf == -2 || cur->_bf == 1)普通單旋是不能解決問(wèn)題的，需要使用到雙旋。

如果使用單旋的話是沒(méi)有多大作用的，做無(wú)用功。我們使用單旋處理的情況是一邊獨(dú)高，而不是那邊高，這邊高。對(duì)此可以先對(duì)內(nèi)部旋轉(zhuǎn)變成單獨(dú)一邊高，再使用單旋進(jìn)行調(diào)整AVL樹。

3.3.1 新節(jié)點(diǎn)插入較高左子樹的右側(cè)–左右:先左單旋再右單旋

場(chǎng)景:parent->_bf == -2 && cur->_bf == 1

這里可以直接復(fù)用實(shí)現(xiàn)好單旋的接口，但是需要對(duì)平衡因子進(jìn)行調(diào)整，這里平衡因子可以通過(guò)結(jié)論直接修改。

3.3.2 根據(jù)結(jié)論修改AVL樹節(jié)點(diǎn)平衡因子

通過(guò)圖中對(duì)于不同情況的分析，對(duì)于修改平衡因子的結(jié)果是根據(jù)SubLR平衡因子特殊值決定的。b、c分別給誰(shuí)，會(huì)影響平衡因子的分配。

3.3.3 新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左：先右單旋再左單旋

場(chǎng)景:parent->_bf == 2 && cur->_bf == -1

這里還是需要根據(jù)60這塊的平衡因子去判斷的，b c分別給誰(shuí)，會(huì)影響平衡因子的分配。左邊新增兩次旋轉(zhuǎn)給到右邊，右邊新增兩次旋轉(zhuǎn)給到左邊，通過(guò)結(jié)論最后修改平衡因子。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;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 == 0){parent->_bf = 0;SubL->_bf = 0;SubLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;SubL->_bf = -1;SubLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;SubL->_bf = 0;SubLR->_bf = 0;}else{assert(false);}
}

3.3.4 小總結(jié)

假如以pParent為根的子樹不平衡，即pParent的平衡因子為2或者-2，分以下情況考慮 ：

1. pParent的平衡因子為2，說(shuō)明pParent的右子樹高，設(shè)pParent的右子樹的根為pSubR

• 當(dāng)pSubR的平衡因子為1時(shí)，執(zhí)行左單旋
• 當(dāng)pSubR的平衡因子為-1時(shí)，執(zhí)行右左雙旋

2. pParent的平衡因子為-2，說(shuō)明pParent的左子樹高，設(shè)pParent的左子樹的根為pSubL

• 當(dāng)pSubL的平衡因子為-1是，執(zhí)行右單旋
• 當(dāng)pSubL的平衡因子為1時(shí)，執(zhí)行左右雙旋

旋轉(zhuǎn)完成后，原pParent為根的子樹個(gè)高度降低，已經(jīng)平衡，不需要再向上更新

四、AVL樹的驗(yàn)證

AVL樹是在二叉搜索樹的基礎(chǔ)上加入了平衡性的限制，因此要驗(yàn)證AVL樹，可以分為兩步:驗(yàn)證是否為二叉搜索樹，驗(yàn)證是否為平衡樹

4.1 驗(yàn)證其為二叉搜索樹

如果中序遍歷可得到一個(gè)有序的序列，就說(shuō)明為二叉搜索樹

void InOder()
{_InOder(_root);cout << endl;
}private:
void _InOder(Node* _root)
{if (_root == nullptr){return;}InOder(_root->_left);cout << _root->_kv.first << " " << _root->_kv.second << endl;InOder(_root->_right);
}

這里將中序遍歷實(shí)現(xiàn)邏輯封裝到私有成員函數(shù)中隱藏它的具體實(shí)現(xiàn)細(xì)節(jié)，使得外部用戶無(wú)法直接訪問(wèn)該函數(shù)，提高了代碼的安全性和可維護(hù)性，符合面向?qū)ο缶幊痰姆庋b性原則。這里外部訪問(wèn)中序遍歷接口，只是傳遞了節(jié)點(diǎn)指針的副本，而不修改任何節(jié)指針的實(shí)際值。

4.2 驗(yàn)證其為平衡樹

規(guī)則:

• 每個(gè)節(jié)點(diǎn)子樹高度差的絕對(duì)值不超過(guò)1(注意節(jié)點(diǎn)種種那個(gè)如果沒(méi)有平衡因子)
• 節(jié)點(diǎn)的平衡因子是否計(jì)算正確

bool IsBalance()
{return _IsBalance(_root);
}int Height()
{return _Height(_root);
}int Size()
{return _Size(_root);
}private:
int _Size(Node* root)
{return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}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 leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 順便檢查一下平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);
}void _InOder(Node* _root)
{if (_root == nullptr){return;}InOder(_root->_left);cout << _root->_kv.first << " " << _root->_kv.second << endl;InOder(_root->_right);
}

五、AVL樹的刪除(了解 )

因?yàn)锳VL樹也是二叉搜索樹，可按照二叉搜索樹的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不錯(cuò)與刪除不同的時(shí)，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置 ，這里調(diào)正平衡因子的邏輯就需要反過(guò)來(lái)，同時(shí)參考下二叉搜索樹的刪除操作。

六、AVL樹的性能

AVL樹是一棵絕對(duì)平衡的二叉搜索樹，其要求每個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值都不超過(guò)1，這樣可以保證查詢時(shí)高效的時(shí)間復(fù)雜度，即O(log^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)的(即不會(huì)改變)，可以考慮AVL樹，但一個(gè)結(jié)構(gòu)經(jīng)常修改，就不太適合

補(bǔ)充調(diào)式小技巧:

void TestAVLTree1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t1;for (auto e : a){/*if (e == 4){int i = 0;}*/// 1、先看是插入誰(shuí)導(dǎo)致出現(xiàn)的問(wèn)題// 2、打條件斷點(diǎn)，畫出插入前的樹// 3、單步跟蹤，對(duì)比圖一一分析細(xì)節(jié)原因t1.Insert({e,e});cout <<"Insert:"<< e<<"->"<< t1.IsBalance() << endl;}t1.InOrder();cout << t1.IsBalance() << endl;
}

七、AVLTree.h

#pragma once
#include <assert.h>
#include <iostream>
using namespace std;//設(shè)置默認(rèn)權(quán)限為公用的結(jié)構(gòu)體
template<class K, class V>struct AVLTreeNode{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;//主要類型AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}};template<class K, class V>class AVLTree{typedef AVLTreeNode<K, V> Node;public: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{//返回當(dāng)前節(jié)點(diǎn)的指針return cur;}}return nullptr;}bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}//也是查找需要插入的地方，進(jìn)行插入Node* parent = nullptr;Node* cur = _root;//目的就是讓cur走到合適的空位置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{assert(!cur);}}//需要將這個(gè)節(jié)點(diǎn)連接起來(lái)cur = new Node(kv);cur->_parent = parent;if (parent->kv.first > cur->_kv.first){parent->_left = cur;}else if (parent->kv.first < cur->_kv.first){parent->_right = cur;}//上述完成了插入的邏輯，調(diào)正平衡因子while (parent){//平衡因子的規(guī)則if (parent->_left == cur){parent->_bf--;}else if (parent->_right == cur){parent->_bf++;}//判斷是否回到父親節(jié)點(diǎn)改動(dòng)if (parent->_bf == 0){//沒(méi)有啥問(wèn)題，可以跳出程序break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}//出現(xiàn)問(wèn)題,這種情況是由情況二變化過(guò)來(lái)的，那么就是說(shuō)，cur和parent向上移動(dòng)了else if (parent->_bf == 2 || parent->_bf == -2){//這里根據(jù)規(guī)律，去固定改變平衡因子if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}//雙旋if (parent->_bf == 2 &&  cur->_bf == -1){RotateRL(parent);}if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}}void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;if (SubLR)SubLR->_parent = parent;SubL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = SubL;if (parent == _root){SubL = _root;SubL->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubL;}else if (ppNode->_right == parent){ppNode->_right = SubL;}SubL->_parant = ppNode;}SubL->_bf = 0;parent->_bf = 0;}void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL)SubR->_parent = parent;SubR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = SubR;if (parent == _root){SubR = _root;SubR->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = SubR;}else if (ppNode->_right == parent){ppNode->_right = SubR;}SubR->_parant = ppNode;}SubR->_bf = 0;parent->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;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 == 0){parent->_bf = 0;SubL->_bf = 0;SubLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;SubL->_bf = -1;SubLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;SubL->_bf = 0;SubLR->_bf = 0;}else{assert(false);}}void InOder(){_InOder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}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 leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}// 順便檢查一下平衡因子是否正確if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOder(Node* _root){if (_root == nullptr){return;}InOder(_root->_left);cout << _root->_kv.first << " " << _root->_kv.second << endl;InOder(_root->_right);}private:Node* _root = nullptr;};void AVLTest1()
{AVLTree<int, int> at;
}

---

以上就是本篇文章的所有內(nèi)容，在此感謝大家的觀看！這里是高階數(shù)據(jù)結(jié)構(gòu)筆記，希望對(duì)你在學(xué)習(xí)高階數(shù)據(jù)結(jié)構(gòu)旅途中有所幫助！