前面我們對(duì) map / multimap / set / multiset 進(jìn)行了簡(jiǎn)單的介紹，可以發(fā)現(xiàn)，這幾個(gè)容器有個(gè)共同點(diǎn)是：其底層都是按照二叉搜索樹(shù)來(lái)實(shí)現(xiàn)的。但是二叉搜索樹(shù)有其自身的缺陷，假如往樹(shù)中插入的元素有序或者接近有序，二叉搜索樹(shù)就會(huì)退化成單支樹(shù)，時(shí)間復(fù)雜度會(huì)退化成 O(N)，因此 map、set 等關(guān)聯(lián)式容器的底層結(jié)構(gòu)是對(duì)二叉樹(shù)進(jìn)行了平衡處理，即采用 平衡樹(shù) 來(lái)實(shí)現(xiàn)。
一、AVL樹(shù)（高度平衡二叉搜索樹(shù)）
1、概念
二叉搜索樹(shù)雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹(shù)將退化為單支樹(shù)，查找元素相當(dāng)于在順序表中搜索元素，效率低下。
- 最優(yōu)情況下，有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)為完全二叉樹(shù)，查找效率為：O(log?N)。
- 最差情況下，有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)退化為單支樹(shù)，查找效率為：O(N)。
因此，兩位俄羅斯的數(shù)學(xué)家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年發(fā)明了一種解決上述問(wèn)題的方法：當(dāng)向二叉搜索樹(shù)中 插入新結(jié)點(diǎn) 后，如果能 保證每個(gè)結(jié)點(diǎn)的左右子樹(shù)高度之差的絕對(duì)值不超過(guò) 1 （需要對(duì)樹(shù)中的結(jié)點(diǎn)進(jìn)行調(diào)整），即可降低樹(shù)的高度，從而減少平均 搜索長(zhǎng)度。
一棵 AVL 樹(shù)或者是空樹(shù)，或者是具有以下性質(zhì)的二叉搜索樹(shù)：
- 它的左右子樹(shù)都是 AVL 樹(shù)。
- 左右子樹(shù)高度之差（簡(jiǎn)稱(chēng)平衡因子）的絕對(duì)值不超過(guò) 1（-1/0/1）。
如果一棵二叉搜索樹(shù)是高度平衡的，它就是 AVL 樹(shù)。如果它有 n 個(gè)結(jié)點(diǎn)，其高度可保持在 O(log?n)，搜索時(shí)間復(fù)雜度 O(log?n)。
為什么左右子樹(shù)高度差不規(guī)定成0呢？
因?yàn)樵?2、4 等節(jié)點(diǎn)數(shù)的情況下，不可能做到左右高度相等的情況。
2、AVL 樹(shù)節(jié)點(diǎn)的定義
AVL 樹(shù)節(jié)點(diǎn)的定義：
AVL 樹(shù)節(jié)點(diǎn)是一個(gè) 三叉鏈結(jié)構(gòu)，除了 指向左右孩子的指針，還有一個(gè) 指向其父親的指針，數(shù)據(jù)域是鍵值對(duì)，即 pair 對(duì)象，還引入了平衡因子，用來(lái)判斷是否需要進(jìn)行平衡操作。
// AVL樹(shù)節(jié)點(diǎn)的定義（KV模型）
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<T>* _left; ? // 該節(jié)點(diǎn)的左孩子
AVLTreeNode<T>* _right; ?// 該節(jié)點(diǎn)的右孩子
AVLTreeNode<T>* _parent; // 該節(jié)點(diǎn)的雙親指針
pair<K, V> _kv; // 鍵值對(duì)
int _bf; // 該節(jié)點(diǎn)的平衡因子(balance factor) = 右子樹(shù)高度-左子樹(shù)高度
// 構(gòu)造函數(shù)
AVLTreeNode(const pari<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
// AVL樹(shù)的定義（KV模型）
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 成員函數(shù)
private:
Node* _root;
}3、AVL樹(shù)的插入
AVL 樹(shù)就是在二叉搜索樹(shù)的基礎(chǔ)上引入了平衡因子，因此 AVL 樹(shù)也可以看成是二叉搜索樹(shù)。那么 AVL 樹(shù)的插入過(guò)程可以分為兩步：
- 按照二叉搜索樹(shù)的方式插入新節(jié)點(diǎn)到 AVL 樹(shù)中。
- 新節(jié)點(diǎn)插入后，AVL 樹(shù)的平衡性可能會(huì)遭到破壞，此時(shí)就需要更新平衡因子，并檢測(cè)是否破壞了 AVL 樹(shù)的平衡（控制樹(shù)的平衡（旋轉(zhuǎn)操作））。
// 插入節(jié)點(diǎn)
bool Insert(const pair<K, V>& kv)
{
// 如果樹(shù)為空，則直接插入節(jié)點(diǎn)
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
// 如果樹(shù)不為空，找到適合插入節(jié)點(diǎn)的空位置
Node* parent = nullptr; // 記錄當(dāng)前節(jié)點(diǎn)的父親
Node* cur = _root; // 記錄當(dāng)前節(jié)點(diǎn)
while (cur) // while循環(huán)結(jié)束，說(shuō)明找到適合插入節(jié)點(diǎn)的空位置了
{
if(kv.first > cur->_kv.first) // 插入節(jié)點(diǎn)鍵值k大于當(dāng)前節(jié)點(diǎn)
{
parent = cur;
cur = cur->_right;
}
else if(kv.first < cur->_kv.first) // 插入節(jié)點(diǎn)鍵值k小于當(dāng)前節(jié)點(diǎn)
{
parent = cur;
cur = cur->_left;
}
else // 插入節(jié)點(diǎn)鍵值k等于當(dāng)前節(jié)點(diǎn)
{
return false;
}
}
// 插入新節(jié)點(diǎn)
cur = new Node(kv); // 申請(qǐng)新節(jié)點(diǎn)
// 判斷當(dāng)前節(jié)點(diǎn)是父親的左孩子還是右孩子
if (cur->_kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 控制平衡
// 1、更新平衡因子
// ...
return true;
}?更新平衡因子
（1）插入新節(jié)點(diǎn)cur 插入后，parent 的平衡因子一定需要調(diào)整，在插入之前，parent 的平衡因子分為三種情況：-1，0，1，分以下兩種情況：
- 如果 cur 插入到?新節(jié)點(diǎn)父親（parent） 的左側(cè)，只需給 父親（parent） 的平衡因子--（
_bf--）即可。- 如果 cur 插入到 新節(jié)點(diǎn)父親（parent） 的右側(cè)，只需給 父親（parent） 的平衡因子++（
_bf++）即可。
?（2）新節(jié)點(diǎn)父親的平衡因子更新以后，又會(huì)分為 3 種情況：
此時(shí)：parent的平衡因子可能有三種情況：0，正負(fù) 1， 正負(fù) 2。
- 如果更新以后，parent 的平衡因子是 0（則說(shuō)明插入之前 parent 的平衡因子之前一定為 1/-1），說(shuō)明父親所在子樹(shù)高度沒(méi)變（因?yàn)榘寻哪沁吔o填補(bǔ)上了），此時(shí)滿(mǎn)足 AVL 樹(shù)的性質(zhì)，插入成功，不需要繼續(xù)往上更新。
- 如果更新以后，parent 的平衡因子是 1/-1（則說(shuō)明插入之前 parent 的平衡因子?一定為 0），說(shuō)明父親所在子樹(shù)高度增加，需要繼續(xù)往上更新。（最壞情況：往上一直更新到根節(jié)點(diǎn)）。
- 如果更新以后，parent 的平衡因子是 2/-2，說(shuō)明父親所在子樹(shù)出現(xiàn)了不平衡，需要對(duì)其進(jìn)行旋轉(zhuǎn)處理。
// 插入節(jié)點(diǎn)
bool Insert(const pair<K, V>& kv)
{
// 控制平衡
// 1、更新平衡因子
while (parent) // 最壞情況：更新到根節(jié)點(diǎn)
{
? ? // 更新雙親的平衡因子
if (cur == parent->_left) // 新節(jié)點(diǎn)插入在父親的左邊
parent->_bf--;
else // 新節(jié)點(diǎn)插入在父親的右邊
parent->_bf++;
// 更新后檢測(cè)雙親的平衡因子
if (0 == pParent->_bf)
? ? ? { ? ?
? ? ? ? break;
? ? ? }
//else if (1 == parent->_bf || -1 == parent->_bf)
else if (abs(parent->_bf) == 1) // 插入前雙親的平衡因子是0，插入后雙親的平衡因?yàn)闉? 或者 -1 ，說(shuō)明以雙親為根的二叉樹(shù)的高度增加了一層，因此需要繼續(xù)向上調(diào)整
{
cur = parent;
parent = cur->_parent;
}
else if (abs(parent->_bf) == 2) // 雙親的平衡因子為正負(fù)2，違反了AVL樹(shù)的平衡性，需要對(duì)以parent為根的樹(shù)進(jìn)行旋轉(zhuǎn)處理
{
// 1、父節(jié)點(diǎn)的右邊高，左邊低，需要往左旋
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent); // 左單旋
}
// 2、父節(jié)點(diǎn)的左邊高，右邊低，需要往右旋
else if ((parent->_bf == -2 && cur->_bf == -1))
{
RotateR(parent); // 右單旋
}
// 3、父節(jié)點(diǎn)的左邊高，且父節(jié)點(diǎn)左孩子的右邊高
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent); // 左右雙旋
}
// 4、父節(jié)點(diǎn)的右邊高，且父節(jié)點(diǎn)右孩子的左邊高
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent); // 右左雙旋
}
break; // 旋轉(zhuǎn)完成，樹(shù)已平衡，退出循環(huán)
}
// 除了上述3種情況，平衡因子不可能有其它的值，報(bào)錯(cuò)處理
else
{
assert(false);
}
}
return true;
}4、AVL樹(shù)的旋轉(zhuǎn)
如果在一棵原本是平衡的 AVL 樹(shù)中插入一個(gè)新節(jié)點(diǎn)，可能造成不平衡，此時(shí)必須調(diào)整樹(shù)的結(jié)構(gòu)，使之平衡化。根據(jù)節(jié)點(diǎn)插入位置的不同，AVL 樹(shù)的旋轉(zhuǎn)分為四種：
旋轉(zhuǎn)的本質(zhì)：在遵循二叉搜索樹(shù)的規(guī)則下，讓左右均衡，降低整棵樹(shù)的高度。
該進(jìn)行哪種旋轉(zhuǎn)操作？
引發(fā)旋轉(zhuǎn)的路徑是直線就是單旋，如果是折線就是雙旋。
注意：此處看到的樹(shù)，可能是一顆完整的樹(shù)，也可能是一顆子樹(shù)。
（1）新節(jié)點(diǎn)插入較高左子樹(shù)的左側(cè) —— 左左：右單旋
將新的節(jié)點(diǎn)插入到了 parent 左孩子的左子樹(shù)上，導(dǎo)致的不平衡的情況。
上圖在插入前，AVL 樹(shù)是平衡的，新節(jié)點(diǎn)插入到 30 的左子樹(shù)（注意：此處不是左孩子）中，30 左子樹(shù)增加了一層，導(dǎo)致以 60 為根的二叉樹(shù)不平衡，要讓 60 平衡，只能將 60 左子樹(shù)的高度減少一層，右子樹(shù)增加一層，即將左子樹(shù)往上提，這樣 60 轉(zhuǎn)下來(lái)，因?yàn)?60 比 30 大，只能將其放在 30 的右子樹(shù)，而如果 30 有右子樹(shù)，右子樹(shù)根的值一定大于 30，小于 60，只能將其放在 60 的左子樹(shù)，旋轉(zhuǎn)完成后，更新節(jié)點(diǎn)的平衡因子即可。
【引發(fā)右單旋的條件】
- 父親左邊高，右邊低，所以要讓父親往右旋。
- parent 的平衡因子為 -2，parent 左孩子平衡因子為 -1，觀察發(fā)現(xiàn)，平衡因子都是負(fù)數(shù)，說(shuō)明是左邊高，也說(shuō)明了引發(fā)旋轉(zhuǎn)的路徑是一條直線，所以我們要右旋操作。
【右單旋操作】
1、讓 subL 的右子樹(shù) subLR 成為 parent 的左子樹(shù)（因?yàn)?subLR 的右子樹(shù)根節(jié)點(diǎn)值 >?30，<?60）。
2、讓 parent 成為 subL 的右子樹(shù)（因?yàn)?60 >?30）。
3、讓 subL 變成這個(gè)子樹(shù)的根。這一步操作前需要先判斷下：parent 是根節(jié)點(diǎn)，還是一個(gè)普通子樹(shù)
- 如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，則更新 subL 為新的根節(jié)點(diǎn)。
- 如果是普通子樹(shù)（可能是某個(gè)節(jié)點(diǎn)的左子樹(shù)，也可能是右子樹(shù)，這里作一個(gè)判斷），然后更新 subL 為這個(gè)子樹(shù)的根節(jié)點(diǎn)。
4、根據(jù)樹(shù)的結(jié)構(gòu)，更新 parent 和 subL 的平衡因子為 0。
在旋轉(zhuǎn)過(guò)程中，更新雙親指針的指向，有以下幾種情況需要考慮：
- 30 節(jié)點(diǎn)的右孩子可能存在，也可能不存在。（subL 的右子樹(shù) subLR 可能存在，也可能為空。當(dāng)不為空時(shí)才更新 subL 右子樹(shù) subLR 的雙親指針指向）。
- 60 可能是根節(jié)點(diǎn)，也可能是子樹(shù)。（旋轉(zhuǎn)完成后，subL 的雙親節(jié)點(diǎn)，可能是空，也可能是 parent 原先的父節(jié)點(diǎn)。所以在更新 subL 的雙親指針前需要判斷下）。
依次調(diào)整 subLR、parent、subL 的位置和雙親指針的指向。?
// 右單旋
void _RotateR(Node* parent)
{ ?
Node* subL = parent->_left; // subL : parent的左孩子
Node* subLR = subL->_right; // subLR : parent左孩子的右孩子
? ?// 旋轉(zhuǎn)完成之后，讓subL的右子樹(shù)subLR成為parent的左子樹(shù)
parent->_left = subLR;
? ?// 如果subLR存在，更新subLR的雙親指針，指向parent
if (subLR)
{
subLR->_parent = parent;
}
? ?
? ?// 因?yàn)閜arent可能是棵子樹(shù)，因此在更新其雙親前必須先保存parent的父節(jié)點(diǎn)
Node* ppNode = parent->_parent;
? ?
// 讓parent成為subL的右子樹(shù)
subL->_right = parent;
? ?// 更新parent的雙親指針，指向subL
parent->_parent = subL;
? ?// 如果parent是根節(jié)點(diǎn)，根新指向根節(jié)點(diǎn)的指針
if (_root == parent)
{
_root = subL; // 更新subL為新的根
subL->_parent = nullptr; // 更新subL的雙親指針，指向空
}
// parent不是根節(jié)點(diǎn)，就是一個(gè)普通子樹(shù)
else
{
? ? // 判斷parent原先是左孩子還是右孩子
if (ppNode->_left == parent)
{
ppNode->_left = subL; // parent原先的雙親節(jié)點(diǎn)接管subL，subL為這個(gè)子樹(shù)的根
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode; // 更新subL的雙親指針
}
? ?// 根據(jù)調(diào)整后的結(jié)構(gòu)更新部分節(jié)點(diǎn)的平衡因子
parent->_bf = pSubL->_bf = 0;
}（2）新節(jié)點(diǎn)插入較高右子樹(shù)的右側(cè) —— 右右：左單旋
【引發(fā)左單旋的條件】
- 父親右邊高，左邊低，所以要讓父親往左旋。
- parent 的平衡因子為 2，parent 左孩子平衡因子為 1，觀察發(fā)現(xiàn)，平衡因子都是正數(shù)，說(shuō)明是右邊高，也說(shuō)明了引發(fā)旋轉(zhuǎn)的路徑是一條直線，所以我們要右旋操作。
【右單旋操作】
1、讓 subR?的左子樹(shù) subRL 成為 parent 的右子樹(shù)（因?yàn)?subRL 的左子樹(shù)根節(jié)點(diǎn)值 >?30，<?60）。
2、讓 parent 成為 subR?的左子樹(shù)（因?yàn)?30 <?60）。
3、讓 subR?變成這個(gè)子樹(shù)的根。這一步操作前需要先判斷下：parent 是根節(jié)點(diǎn)，還是一個(gè)普通子樹(shù)
- 如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，則更新 subR?為新的根節(jié)點(diǎn)。
- 如果是普通子樹(shù)（可能是某個(gè)節(jié)點(diǎn)的左子樹(shù)，也可能是右子樹(shù)，這里作一個(gè)判斷），然后更新 subR?為這個(gè)子樹(shù)的根節(jié)點(diǎn)。
4、根據(jù)樹(shù)的結(jié)構(gòu)，更新 parent 和 subR?的平衡因子為 0。
在旋轉(zhuǎn)過(guò)程中，更新雙親指針的指向，有以下幾種情況需要考慮：
- subR 的左子樹(shù) subRL 可能存在，也可能為空。（當(dāng)不為空時(shí)才更新 subR 左子樹(shù) subRL 的雙親指針指向）。
- 旋轉(zhuǎn)完成后，subR 的雙親節(jié)點(diǎn)，可能是空，也可能是 parent 原先的父節(jié)點(diǎn)。（所以更新 subR 的雙親指針前需要判斷下）。
依次調(diào)整 subRL、parent、subR 的位置和雙親指針的指向。
// 左單旋
void treeRotateLeft(Node* parent)
{
Node* subR = parent->_right; // subR：父親的右孩子
Node* subRL = subR->_left; // subRL：父親的右孩子的左孩子（大于父親，小于subR）
// 讓subRL成為父親的右子樹(shù)
parent->_right = subRL;
// 如果subRL不為空
if (subRL)
{
subRL->_parent = parent; // 更新subRL雙親指針，指向parent
}
// 因?yàn)閜arent可能是棵子樹(shù)，因此在更新其雙親前必須先保存parent的父節(jié)點(diǎn)
Node* ppNode = parent->_parent;
// 讓parent成為subR的左子樹(shù)
subR->_left = parent;
// 更新parent雙親指針的指向
parent->_parent = subR;
// 判斷parent是不是根節(jié)點(diǎn)
if (parent == _root)
{
_root = subR; // subR為新的根
subR->_parent = nullptr; // subR雙親指針指向空
}
// 不是根節(jié)點(diǎn)，就是一個(gè)普通子樹(shù)
else
{
// 判斷parent原先是左孩子還是右孩子
if (ppNode->_left == parent)
{
ppNode->_left = subR; // parent原先的雙親節(jié)點(diǎn)接管subR，subR為這個(gè)子樹(shù)的根
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode; // 更新subR的雙親指針
}
// 根據(jù)樹(shù)的結(jié)構(gòu)，更新parent和subR的平衡因子
parent->_bf = subR->_bf = 0;
}
（3）新節(jié)點(diǎn)插入較高左子樹(shù)的右側(cè) —— 左右：先左單旋再右單旋（左右雙旋）
將新的節(jié)點(diǎn)插入到了 parent 左孩子的右子樹(shù)上，導(dǎo)致的不平衡的情況。
這時(shí)我們需要的是先對(duì) parent 的右孩子進(jìn)行一次左旋，再對(duì) parent 進(jìn)行一次右旋。
將雙旋變成單旋后再旋轉(zhuǎn)，即：先對(duì) 30 進(jìn)行左單旋，然后再對(duì) 90 進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。
旋轉(zhuǎn)之前，60 的平衡因子可能是 -1/0/1，旋轉(zhuǎn)完成之后，根據(jù)情況對(duì)其他節(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整。
【h == 0】?
【引發(fā)雙旋的條件】
引發(fā)旋轉(zhuǎn)的路徑是直線就是單旋，如果是折線就是雙旋。
parent 的平衡因子為 -2，parent 左孩子的平衡因子為 1，觀察發(fā)現(xiàn)，平衡因子是一負(fù)一正，說(shuō)明左孩子右邊高，父親左邊高，也說(shuō)明了引發(fā)旋轉(zhuǎn)的路徑是一條折線，所以我們要先對(duì)左孩子進(jìn)行左旋操作，再對(duì)父親進(jìn)行右旋操作。
左右雙旋操作后，根據(jù)樹(shù)的結(jié)構(gòu)，更新平衡因子時(shí)，需要注意：
插入新節(jié)點(diǎn)的位置不同，經(jīng)過(guò)左右雙旋后，得到樹(shù)的結(jié)構(gòu)也會(huì)有所不同，平衡因子也會(huì)有所不同，有以下三種情況：
- 新節(jié)點(diǎn)插入到了 parent 左孩子的右子樹(shù)的左邊。
- 新節(jié)點(diǎn)插入到了 parent 左孩子的右子樹(shù)的右邊。
- 新節(jié)點(diǎn)就是 parent 左孩子的右孩子。
這里可以觀察到一個(gè)現(xiàn)象，根據(jù)這個(gè)現(xiàn)象就很好推出旋轉(zhuǎn)后的平衡因子：
節(jié)點(diǎn) 60 的左右子樹(shù)被分走了，左子樹(shù)最終成為了節(jié)點(diǎn) 30 的右子樹(shù)，右子樹(shù)最終成了節(jié)點(diǎn) 90 的左子樹(shù)。
void _RotateLR(PNode pParent)
{
Node* subL = parent->_left; // 記錄parent的左孩子
Node* subLR = subL->_right; // 記錄parent的左孩子的右孩子
? ?
// 旋轉(zhuǎn)之前，因?yàn)椴迦胄鹿?jié)點(diǎn)的位置不同，subLR的平衡因子可能是-1/0/1
int bf = subLR->_bf; // 記錄subLR的平衡因子
? ?
? ?// 先對(duì)parent的左孩子進(jìn)行左單旋
RotateL(parent->_left);
? ?// 再對(duì)parent進(jìn)行右單旋
RotateR(parent);
// 旋轉(zhuǎn)完成之后，根據(jù)情況對(duì)其他節(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整
subLR->_bf = 0;
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
assert(false);
}
}（4）新節(jié)點(diǎn)插入較高右子樹(shù)的左側(cè) —— 右左：先右單旋再左單旋（右左雙旋）???????
將新的節(jié)點(diǎn)插入到了 parent 右孩子的左子樹(shù)上，導(dǎo)致的不平衡的情況。
這時(shí)我們需要的是先對(duì) parent 的右孩子進(jìn)行一次右旋，再對(duì) parent 進(jìn)行一次左旋。
【h == 1】
【引發(fā)雙旋的條件】
引發(fā)旋轉(zhuǎn)的路徑是直線就是單旋，如果是折線就是雙旋。
parent 的平衡因子為 2， parent 右孩子平衡因子為 -1，觀察發(fā)現(xiàn)，平衡因子是一正一負(fù)，說(shuō)明右孩子左邊高，父親右邊高，也說(shuō)明了引發(fā)旋轉(zhuǎn)的路徑是一條折線，所以我們要先對(duì)右孩子進(jìn)行右旋操作，再對(duì)父親進(jìn)行左旋操作。
左右雙旋操作后，根據(jù)樹(shù)的結(jié)構(gòu)，更新平衡因子時(shí)，需要注意：
插入新節(jié)點(diǎn)的位置不同，經(jīng)過(guò)右左雙旋后，得到樹(shù)的結(jié)構(gòu)也會(huì)有所不同，平衡因子也會(huì)有所不同，有以下三種情況：
- 新節(jié)點(diǎn)插入到了?parent 右孩子的左子樹(shù)的左邊。
- 新節(jié)點(diǎn)插入到了 parent 右孩子的左子樹(shù)的右邊。
- 新節(jié)點(diǎn)就是 parent 右孩子的左孩子。
這里可以觀察到一個(gè)現(xiàn)象，根據(jù)這個(gè)現(xiàn)象就很好推出旋轉(zhuǎn)后的平衡因子：
節(jié)點(diǎn) 60 的左右子樹(shù)被分走了，左子樹(shù) b 最終成了節(jié)點(diǎn) 30 的右子樹(shù)，右子樹(shù) c 最終成了節(jié)點(diǎn) 90 的左子樹(shù)。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-734878.html
// 右左雙旋
void treeRotateRL(Node* parent)
{
Node* subR = parent->_right; // 記錄parent的右孩子
Node* subRL = subR->_left; // 記錄parent的右孩子的左孩子
// 旋轉(zhuǎn)之前，因?yàn)椴迦胄鹿?jié)點(diǎn)的位置不同，subRL的平衡因子可能為-1/0/1
int bf = subRL->_bf; // 記錄subRL的平衡因子
RotateR(parent->_right); // 先對(duì)parent的右孩子進(jìn)行右單旋
RotateL(parent); // 再對(duì)parent進(jìn)行左單選
// 旋轉(zhuǎn)完成之后，根據(jù)樹(shù)的結(jié)構(gòu)對(duì)其他節(jié)點(diǎn)的平衡因子進(jìn)行調(diào)整
subRL->_bf = 0;
if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if(bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}【總結(jié)】假如以 parent 為根的子樹(shù)不平衡，即 parent 的平衡因子為 2/-2，分以下情況考慮：1、parent 的平衡因子為 2，說(shuō)明 parent 的右子樹(shù)高，設(shè) parent 的右子樹(shù)的根為 subR。
- 當(dāng) subR 的平衡因子為 1 時(shí)，執(zhí)行左單旋。
- 當(dāng) subR 的平衡因子為 -1 時(shí)，執(zhí)行右左雙旋。
2、parent 的平衡因子為 -2，說(shuō)明 parent 的左子樹(shù)高，設(shè) parent 的左子樹(shù)的根為 subL。
- 當(dāng) subL 的平衡因子為 -1 時(shí)，執(zhí)行右單旋。
- 當(dāng) subL 的平衡因子為 1 時(shí)，執(zhí)行左右雙旋。
旋轉(zhuǎn)完成后，原 parent 為根的子樹(shù)個(gè)高度降低，已經(jīng)平衡，不需要再向上更新。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-734878.html
5、AVL樹(shù)的驗(yàn)證
AVL 樹(shù)是在二叉搜索樹(shù)的基礎(chǔ)上加入了平衡性的限制，因此要驗(yàn)證 AVL 樹(shù)，可以分兩步：
1、驗(yàn)證其為二叉搜索樹(shù)
- 如果中序遍歷可得到一個(gè)有序的序列，就說(shuō)明為二叉搜索樹(shù)。
2、驗(yàn)證其為平衡樹(shù)
- 每個(gè)節(jié)點(diǎn)子樹(shù)高度差的絕對(duì)值不超過(guò) 1（注意節(jié)點(diǎn)中如果沒(méi)有平衡因子）。
- 節(jié)點(diǎn)的平衡因子是否計(jì)算正確。
（1）首先寫(xiě)一個(gè)計(jì)算當(dāng)前樹(shù)高度的函數(shù)
// 計(jì)算當(dāng)前樹(shù)的高度
int Height(Node* root)
{
// 當(dāng)前樹(shù)為空，則高度為0
if (root == nullptr)
return 0;
// 當(dāng)前樹(shù)的高度 = 左右子樹(shù)中高度最大的那個(gè)加1
return max(Height(root->_left), Height(root->_right)) + 1;
}（2）檢查AVL樹(shù)是否平衡：【思路一】自頂向下的暴力解法
bool IsBalance1()
{
return _IsBalance(_root);
}
bool _IsBalance1(Node* root)
{
// 當(dāng)前樹(shù)為空，說(shuō)明是平衡的
if (root == nullptr)
return true;
// 當(dāng)前樹(shù)不為空，計(jì)算左右子樹(shù)的高度
int leftHT = Height(root->_left);
int rightHT = Height(root->_right);
int diff = rightHT - leftHT;
if (diff != root->_bf) // 檢查當(dāng)前樹(shù)的平衡因子是否計(jì)算正確
{
cout << root->_kv.first << "平衡因子異常" << endl;
return false;
}
// 左右子樹(shù)高度相減的絕對(duì)值小于2，說(shuō)明當(dāng)前樹(shù)是平衡的，則繼續(xù)往下判斷其它子樹(shù)
return abs(diff) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}（3）檢查AVL樹(shù)是否平衡【思路二】自底向上的高效解法（動(dòng)態(tài)規(guī)劃，前一個(gè)子問(wèn)題的解，能夠用于后一個(gè)問(wèn)題求解）
bool IsBalance2()
{
return _IsBalance2(_root) != -1;
}
int _IsBalance2(Node* root)
{
// 先判斷當(dāng)前樹(shù)的左、右子樹(shù)是否平衡，再判斷當(dāng)前樹(shù)是否平衡
// 不平衡返回-1，平衡則返回當(dāng)前樹(shù)的高度
// 當(dāng)前樹(shù)為空，返回高度0
if (root == nullptr)
return 0;
// 當(dāng)前樹(shù)不為空，分別計(jì)算左右子樹(shù)的高度
int leftHeight = _IsBalance2(root->_left);
int rightHeight = _IsBalance2(root->_right);
int diff = rightHT - leftHT;
if (diff != root->_bf) // 檢查當(dāng)前樹(shù)的平衡因子是否計(jì)算正確
{
cout << "平衡因子異常:" << root->_kv.first << endl;
}
// 左子樹(shù)高度等于-1、右子樹(shù)高度等于-1、左右子樹(shù)高度差的絕對(duì)值大于1，說(shuō)明當(dāng)前樹(shù)不平衡
if (leftHeight == -1 || rightHeight == -1 || abs(diff) > 1)
return -1;
// 運(yùn)行到這里來(lái)了，說(shuō)明當(dāng)前樹(shù)是平衡的，返回當(dāng)前樹(shù)的高度
return max(leftHeight, rightHeight) + 1;
}（4）【思路三】
bool _IsBalanceTree3(Node* root)
{
// 空樹(shù)也是AVL樹(shù)
if (nullptr == root)
return true;
? ?
// 計(jì)算pRoot節(jié)點(diǎn)的平衡因子：即pRoot左右子樹(shù)的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果計(jì)算出的平衡因子與pRoot的平衡因子不相等，或者pRoot平衡因子的絕對(duì)值超過(guò)1，則一定不是AVL樹(shù)
if (diff != root->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL樹(shù)，則該樹(shù)一定是AVL樹(shù)
return _IsBalanceTree3(root->_left) && _IsBalanceTree3(root->_right);
}3、驗(yàn)證用例
- 常規(guī)場(chǎng)景 1：{16, 3, 7, 11, 9, 26, 18, 14, 15}
- 特殊場(chǎng)景 2：{4, 2, 6, 1, 3, 5, 15, 7, 16,?14}
6、AVL樹(shù)的刪除（了解）?
因?yàn)?AVL 樹(shù)也是二叉搜索樹(shù)，可按照二叉搜索樹(shù)的方式將節(jié)點(diǎn)刪除，然后再更新平衡因子，只不過(guò)與刪除不同的是，刪除節(jié)點(diǎn)后的平衡因子更新，最差情況下一直要調(diào)整到根節(jié)點(diǎn)的位置。具體實(shí)現(xiàn)可參考《算法導(dǎo)論》或《數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο蠓椒ㄅcC++描述》殷人昆版。
7、AVL 樹(shù)的性能
AVL 樹(shù)是一棵絕對(duì)平衡的二叉搜索樹(shù)，其要求每個(gè)節(jié)點(diǎn)的左右子樹(shù)高度差的絕對(duì)值都不超過(guò) 1，這樣可以保證查詢(xún)時(shí)高效的時(shí)間復(fù)雜度，即 O(logN)。但是如果要對(duì) AVL 樹(shù)做一些結(jié)構(gòu)修改的操作，性能非常低下，比如：插入時(shí)要維護(hù)其絕對(duì)平衡，旋轉(zhuǎn)的次數(shù)比較多，更差的是在刪除時(shí)，有可能一直要讓旋轉(zhuǎn)持續(xù)到根的位置。因此，如果需要一種查詢(xún)高效且有序的數(shù)據(jù)結(jié)構(gòu)，而且數(shù)據(jù)的個(gè)數(shù)為靜態(tài)的（即不會(huì)改變），可以考慮 AVL 樹(shù)，但一個(gè)結(jié)構(gòu)經(jīng)常修改，就不太適合。
到了這里，關(guān)于【C++】map&set的底層結(jié)構(gòu) -- AVL樹(shù)（高度平衡二叉搜索樹(shù)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![數(shù)據(jù)結(jié)構(gòu)07：查找[C++][平衡二叉排序樹(shù)AVL]](https://imgs.yssmx.com/Uploads/2024/02/502021-1.png)
