二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。
因此，兩位俄羅斯的數(shù)學家G.M.Adelson-Velskii和E.M.Landis在 1962 年發(fā)明了一種解決上述問題的方法：當向二叉搜索樹中插入新結點后，如果能保證每個結點的左右子樹高度之差的絕對值不超過 1（需要對樹中的結點進行調整），即可降低樹的高度，從而減少平均搜索長度。
平衡二叉樹（Balanced Binary Tree 或 Height-Balanced Tree）又稱為 AVL 樹，其實就是一顆 平衡的二叉排序樹 ，解決了二叉查找樹的不平衡問題，即斜樹。
AVL樹或者是一顆空樹，或者是具有下列性質的二叉搜索樹：
舉個例子，下圖就是一顆典型的 AVL 樹，每個節(jié)點旁邊都標注了平衡因子：
上面是一顆典型的平衡二叉樹，首先它是一顆二叉排序樹，其次每一個結點的平衡因子都是 -1，0，1 三個數(shù)當中的一個。
紅色的數(shù)字為結點的平衡因子，對于任意一個葉子結點而言，其左右孩子都為空，左子樹的深度為 0 ，右子樹的深度為 0 ，所以 AVL樹當中的葉子結點的平衡因子都是 0 ；
其他結點的平衡因子同樣通過 右子樹深度減去左子樹深度 可以求得，比如結點 3 的 左子樹深度為 2，右子樹深度為1 ，則平衡因子為 1 ? 2 = ? 1 1 - 2 = -1 1?2=?1。
如果一棵二叉搜索樹是高度平衡的，它就是 AVL 樹。如果它有 n 個結點，其高度可保持在 O ( l o g n ) O(logn) O(logn)，搜索時間復雜度 O ( l o g n O(log n O(logn)。
再來看看不平衡的情況，如下面這顆樹：
上圖中就是不平衡的二叉排序樹，非 AVL樹 。結點 5 的平衡因子為 -2，該平衡因子是結點 5 右子樹深度 2 減去左子樹深度 4 所得；
我們要學習的就是將這種不平衡的二叉搜索樹轉化為 AVL樹。
2. AVL樹的結點我們直接按照 KV 模型來構造 AVL 樹，需要把結點定義為 三叉鏈結構，并在每個結點當中引入平衡因子（右子樹高度-左子樹高度）。
對于結點的構造函數(shù)，由于新構造結點的左右子樹均為空樹，所以只需要將新構造結點的平衡因子初始設置為 0 即可。
代碼示例
重慶分公司
重慶分公司
templatestruct AVLTreeNode
{// 存儲的鍵值對
pair_kv;
// 三叉鏈
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
// 平衡因子(balance factor)
int _bf; // 右子樹高度 - 左子樹高度
// 構造函數(shù)
AVLTreeNode(const pair& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
}; 對平衡二叉樹的插入操作而言，其本質上比二叉搜索樹的插入操作多了一個平衡操作，解決了二叉搜索樹插入操作可能出現(xiàn)的斜樹，不平衡問題。
那么 AVL 樹的插入過程可以分為兩步：
當 AVL 樹插入一個新結點以后，需要更新插入結點的祖先的平衡因子，因為新結點（也就是葉子結點）的平衡因子為 0，但是它影響的是它的父親，它父親的父親…，所以要更新到祖先結點。
所以我們要從新增結點開始，往上沿著祖先路徑更新，那么更新的規(guī)則如下：
+1即可-1即可為什么呢？因為平衡因子的計算方法是：右子樹高度 - 左子樹高度，如果插入在右邊，那么最后的結果肯定是要++，反之，則--。
當 parent 的平衡因子更新完以后，可能出現(xiàn)三種情況：0，正負 1，正負 2。
（1）parent 的平衡因子為 0
如果 parent 的平衡因子為 0，說明插入之前 parent 的平衡因子為正負 1，插入后被調整成 0，此時滿足 AVL 樹的性質，則插入成功。
如下圖所示，插入后使得 parent 左右子樹的高度相等了，此操作并沒有改變以 parent 為根結點的子樹的高度，從而不會影響 parent 的父結點的平衡因子，因此無需繼續(xù)往上更新平衡因子。
（2）如果 parent 的平衡因子為正負 1
如果 parent 的平衡因子為正負 1，說明插入前 parent 的平衡因子一定為 0，插入后被更新成正負 1。
如下圖所示，當新增一個結點以后，parent 的平衡因子從 0 變成了 1，說明新結點的插入使得 parent 的右子樹增高了，即改變了以 parent 為根結點的子樹的高度，從而會影響 parent 的父結點的平衡因子，因此需要繼續(xù)往上更新平衡因子。
如下圖所示，當新增一個結點以后，parent 的平衡因子從 0 變成了 -1，說明新結點的插入使得 parent 的左子樹增高了，即改變了以 parent 為根結點的子樹的高度，從而會影響 parent 的父結點的平衡因子，因此需要繼續(xù)往上更新平衡因子。
進而引出了下面的第 3 種情況。
（3）如果 parent 的平衡因子為正負 2
如果 parent 的平衡因子為 -2，此時 parent 結點的左右子樹高度之差的絕對值已經(jīng)超過 1 了，則 parent 的平衡因子違反平衡樹的性質，那么就停止更新，需要對其進行旋轉處。
如果 parent 的平衡因子為 2，此時 parent 結點的左右子樹高度之差的絕對值已經(jīng)超過 1 了，則 parent 的平衡因子違反平衡樹的性質，那么就停止更新，需要對其進行旋轉處。
可以看到，當 parent 的平衡因子為正負 2 時，cur 的平衡因子必定是正負 1 而不會是 0。
🍑 插入函數(shù)的實現(xiàn)上面我們分析了，如果在更新平衡因子的過程當中，出現(xiàn)了平衡因子為正負 2 的結點，此時需要對 以該結點為根結點的樹 進行旋轉處理（待會兒再講旋轉）。
我們定義一個cur用來表示 新增結點，定義一個parent用來表示 新增結點的父親結點。
那么我們更新平衡因子時，第一個要更新的就是 parent 結點的平衡因子，更新完 parent 結點的平衡因子后，若是需要繼續(xù)往上進行平衡因子的更新，那么要執(zhí)行以下操作：
if (parent->_bf == 1 || parent->_bf == -1)
{cur = cur->_parent; // cur指向了它的父親
parent = parent->_parent; // 它的父親指向了它的祖先
}可以看到，我們之所以將 AVL 樹結點的結構設置為三叉鏈結構，是因為我們可以很方便的通過父指針找到其父結點，進而對其平衡因子進行更新。
而當 parent 的平衡因子為正負 2 時，我們需要對其進行旋轉操作，當旋轉完成以后，就無需繼續(xù)往上更新平衡因子了，即樹的高度沒有發(fā)生變化，也就不會影響其父結點的平衡因子了。
if (parent->_bf == 2 || parent->_bf == -2)
{// 旋轉的四種處理方式
// 1.左單旋
// 2.右單旋
// 3.左右雙旋
// 4.右左雙旋
// 當旋轉完成以后，直接跳出
break;
}代碼示例
public:
// 插入函數(shù)
bool Insert(const pair& kv)
{// 如果AVL樹是空樹，把插入節(jié)點直接作為根節(jié)點
if (_root == nullptr)
{ _root = new Node(kv);
_root->_bf = 0;
return true;
}
// 1.按照二叉搜索樹的規(guī)則插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{ if (cur->_kv.first< kv.first) // 待插入節(jié)點的key值大于當前節(jié)點的key值
{ // 往右子樹走
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first >kv.first) // 待插入節(jié)點的key值小于當前節(jié)點的key值
{ // 往左子樹走
parent = cur;
cur = cur->_left;
}
else // 待插入節(jié)點的key值等于當前節(jié)點的key值
{ return false; // 插入失敗，返回false
}
}
// 2.當循環(huán)結束，說明cur找到了空的位置，那么就插入
cur = new Node(kv); // 構造一個新節(jié)點
if (parent->_kv.first< kv.first) // 如果新節(jié)點的key值大于當前parent節(jié)點的key值
{ // 就把新節(jié)點鏈接到parent的右邊
parent->_right = cur;
}
else // 如果新節(jié)點的key值小于當前parent節(jié)點的key值
{ // 就把新節(jié)點鏈接到parent的左邊
parent->_left = cur;
}
cur->_parent = parent; // 別忘了把新節(jié)點里面的_parent指向parent(因為我們定義的是一個三叉鏈)
// 3.更新平衡因子,如果出現(xiàn)不平衡,則需要進行旋轉
while (parent) // 最遠要更新到根節(jié)點去
{ if (cur == parent->_right) // 如果cur插在parent的右邊，說明parent的右子樹增高
{ parent->_bf++; // 那么parent的平衡因子要++
}
else // 如果cur插在parent的左邊，說明parent的左子樹增高
{ parent->_bf--; // 那么parent的平衡因子要--
}
// 判斷是否更新結束，或者是否需要進行旋轉
if (parent->_bf == 0) // 如果parent的bf等于0，說明左右子樹高度一致，就更新結束(原因是新插入的節(jié)點把parent左右子樹中矮的那一邊給填補了）
{ // 高度不變,更新結束
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 繼續(xù)往上更新平衡因子(插入節(jié)點導致某一邊變高了，說明parent所在的子樹高度改變了)
{ // 子樹的高度變了，就要繼續(xù)往上更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 說明插入節(jié)點導致本來高的一邊又變高了，子樹不平衡了，那么此時需要做旋轉處理
{ // 旋轉的四種處理方式
// 1.左單旋
// 2.右單旋
// 3.左右雙旋
// 4.右左雙旋
// 旋轉完成，跳出
break;
}
else
{ // 如果程序走到了這里，說明在插入節(jié)點之前AVL樹就存在不平衡的子樹，也就是存在平衡因子 >= 2的節(jié)點
// 所以這里加一個斷言進行處理
assert(false);
}
}
// 插入成功，返回true
return true;
} 如果在一棵原本是平衡的 AVL 樹中插入一個新節(jié)點，可能造成不平衡，此時必須調整樹的結構，使之平衡化。
根據(jù)節(jié)點插入位置的不同，AVL 樹的旋轉分為四種：
其實我們只要搞懂 LL 和 RR 就好了，因為 LR 和 RL 都是由它們演變而來的。
不管是什么旋轉，都必須滿足兩點原則：
下面是一個 AVL 樹的抽象圖，長方形條代表的是子樹，h表示 a，b，c 三顆子樹的高度。
現(xiàn)在我們在 c 子樹的中插入一個新結點，那么此時 c 子樹的高度就變成了 h + 1，同時結點 60 的平衡因子為 1，結點 30 的平衡因子為 2，此時右邊的高度大于左邊的高度，需要進行左單旋。
左單旋的步驟如下：
左單旋圖如下所示：
經(jīng)過旋轉以后，它們的平衡因子就發(fā)生了變化：
這樣旋轉以后還滿足二叉搜索樹的性質嗎？當面滿足，原因如下：
什么時候需要用到左旋操作呢？可以看到，當 parent 的平衡因子為 2，cur 的平衡因子為 1 時，需要進行左單旋。并且經(jīng)過左單旋后，樹的高度沒有發(fā)生變化，所以左單旋后無需繼續(xù)往上更新平衡因子。
左單旋動圖演示：
可以看到，我們在 32 的右邊插入一個值為 35 的新節(jié)點，那么此時 32 的平衡因子從 0 變成了 1，29 的平衡因子從 1 變成了 2，出現(xiàn)了右邊高，左邊低的局面，所以需要進行左單旋
代碼示例
private:
// 左單旋（右邊高需要左單旋）
void RotateL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppNode = parent->_parent; // 先保存parent的parent
// 1.建立parent和subRL之間的關系
parent->_right = subRL;
if (subRL) // 如果subRL節(jié)點不為空，那么要更新它的parent
{ subRL->_parent = parent;
}
// 2.建立subR和parent之間的關系
subR->_left = parent;
parent->_parent = subR;
// 3.建立ppNode和subR之間的關系（分情況討論parent是整顆樹的根，還是局部子樹）
if (parent == _root) // 當parent是根節(jié)點時
{ _root = subR; // subR就變成了新的根節(jié)點
_root->_parent = nullptr; // 根節(jié)點的的parent為空
}
else // 當parent是整個樹的局部子樹時
{ if (parent == ppNode->_left) // 如果parent在ppNode的左邊
{ ppNode->_left = subR; // 那么subR就是parent的左子樹
}
else // 如果parent在ppNode的右邊
{ ppNode->_right = subR; // 那么subR就是parent的右子樹
}
subR->_parent = ppNode; // subR的parent還要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}還有一點需要注意，如果在旋轉前 parent（30） 就是樹的根，那么此時只需要更新根結點為 subR（60）即可。
如果 parent（30） 只是整顆樹局部的一顆子樹，那么此時就需要看 30 是它父親的左子樹還是右子樹，然后再和 subR 鏈接起來，如下圖所示：
下面是一個 AVL 樹的抽象圖，長方形條代表的是子樹，h表示 a，b，c 三顆子樹的高度。
現(xiàn)在我們在 a 子樹的中插入一個新結點，那么此時 a 子樹的高度就變成了 h + 1，同時結點 60 的平衡因子為 -2，結點 30 的平衡因子為 -1，此時左邊的高度大于右邊的高度，需要進行右單旋。
右單旋的步驟如下：
右單旋圖如下所示：
經(jīng)過旋轉以后，它們的平衡因子就發(fā)生了變化：
這樣旋轉以后還滿足二叉搜索樹的性質嗎？當面滿足，原因如下：
什么時候需要用到右旋操作呢？可以看到，當 parent 的平衡因子為 -2，cur 的平衡因子為 -1 時，需要進行右單旋。并且經(jīng)過右單旋后，樹的高度沒有發(fā)生變化，所以右單旋后無需繼續(xù)往上更新平衡因子。
右單旋動圖演示：
可以看到，我們在 9 的左邊插入一個值為 5 的新節(jié)點，那么此時 9 的平衡因子從 0 變成了 -1，11 的平衡因子從 -1 變成了 -2，出現(xiàn)了左邊高，右邊低的局面，所以需要進行右單旋
代碼示例
private:
// 右單旋（左邊高就右單旋）
void RotateR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
// 1.建立parent和subLR之間的關系
parent->_left = subLR;
if (subLR) // 如果subLR節(jié)點不為空，那么要更新它的parent
{ subLR->_parent = parent;
}
// 2.建立subL和parent之間的關系
subL->_right = parent;
parent->_parent = subL;
// 3.建立ppNode和subL之間的關系（分情況討論parent是整顆樹的根，還是局部子樹）
if (parent == _root) // 當parent是根節(jié)點時
{ _root = subL; // subL就變成了新的根節(jié)點
_root->_parent = nullptr; // 根節(jié)點的的parent為空
}
else // 當parent是整個樹的局部子樹時
{ if (parent == ppNode->_left) // 如果parent在ppNode的左邊
{ ppNode->_left = subL; // 那么subL就是parent的左子樹
}
else // 如果parent在ppNode的右邊
{ ppNode->_right = subL; // 那么subL就是parent的右子樹
}
subL->_parent = ppNode; // subR的parent還要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subL->_bf = 0;
}需要注意，如果在旋轉前 parent（60） 就是樹的根，那么此時只需要更新根結點為 subL（30）即可。
如果 parent（60） 只是整顆樹局部的一顆子樹，那么此時就需要看 60 是它父親的左子樹還是右子樹，然后再和 subL 鏈接起來。
🍑 左右雙旋下面是一個 AVL 樹的抽象圖，長方形條代表的是子樹，h表示 a 和 d 兩顆子樹的高度，h-1代表 b 和 c 兩顆子樹的高度。
現(xiàn)在我們在 b 子樹的中插入一個新結點，那么此時 b 子樹的高度就變成了 h，同時結點 60 的平衡因子變成了 -1，結點 30 的平衡因子變成了 1，結點 90 的平衡因子變成了 -2，此時如果單純的以結點 90 為旋轉點進行左單旋或者右單旋以后，那么仍然不是 AVL 樹，所以需要采取左右雙旋的方式。
注意：在 b 子樹當中新增結點，或是在 c 子樹當中新增結點，均會引發(fā)左右雙旋，這里以在 b 子樹當中新增結點為例。
左右雙旋的步驟如下：
（1）以 30 為旋轉點進行左單旋
（2）以 90 為旋轉點進行右單旋
左右雙旋后，實際上就是讓 subLR 的左子樹和右子樹，分別作為 subL 和 parent 的右子樹和左子樹，再讓 subL 和 parent 分別作為 subLR 的左右子樹，最后讓 subLR 作為整個子樹的根
這樣旋轉以后還滿足二叉搜索樹的性質嗎？當面滿足，原因如下：
左右雙旋后，平衡因子的更新隨著 subLR 原始平衡因子的不同分為以下三種情況：
（1）當 subLR 原始平衡因子是 -1 時，左右雙旋后 parent、subL、subLR 的平衡因子分別更新為 1、0、0
（2）當 subLR 原始平衡因子是 1 時，左右雙旋后 parent、subL、subLR 的平衡因子分別更新為 0、-1、0
（3）當 subLR 原始平衡因子是 0 時（說明 subLR 為新增結點），左右雙旋后 parent、subL、subLR 的平衡因子分別更新為0、0、0
可以看到，經(jīng)過左右雙旋后，樹的高度沒有發(fā)生變化，所以左右雙旋后無需繼續(xù)往上更新平衡因子。
代碼示例
private:
// 左右雙旋（先左單旋，再右單旋）
void RotateLR(Node* parent)
{Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
// 1.先以subL為旋轉點進行左單旋
RotateL(parent->_left);
// 2.再以parent為旋轉點進行右單旋
RotateR(parent);
// 3.更新平衡因子
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
{ // 如果走到了這里，說明subLR的平衡因子在旋轉前就有問題
assert(false);
}
}下面是一個 AVL 樹的抽象圖，長方形條代表的是子樹，h表示 a 和 d 兩顆子樹的高度，h-1代表 b 和 c 兩顆子樹的高度。
現(xiàn)在我們在 c 子樹的中插入一個新結點，那么此時 c 子樹的高度就變成了 h，同時結點 60 的平衡因子變成了 1，結點 00 的平衡因子變成了 -1，結點 30 的平衡因子變成了 -2，此時如果單純的以結點 30 為旋轉點進行左單旋或者右單旋以后，那么仍然不是 AVL 樹，所以需要采取右左雙旋的方式。
注意：在 b 子樹當中新增結點，或是在 c 子樹當中新增結點，均會引發(fā)右左雙旋，這里以在 c 子樹當中新增結點為例。
右左雙旋的步驟如下：
（1）以 90 為旋轉點進行右單旋
（2）以 30 為旋轉點進行左單旋
右左雙旋后，實際上就是讓 subRL 的左子樹和右子樹，分別作為 parent 和 subR 的右子樹和左子樹，再讓 parent 和 subR 分別作為 subRL 的左右子樹，最后讓 subRL 作為整個子樹的根。
這樣旋轉以后還滿足二叉搜索樹的性質嗎？當面滿足，原因如下：
右左雙旋后，平衡因子的更新隨著 subLR 原始平衡因子的不同分為以下三種情況：
（1）當 subRL 原始平衡因子是 1 時，左右雙旋后 parent、subR、subRL 的平衡因子分別更新為 -1、0、0
（2）當 subRL 原始平衡因子是 -1 時，左右雙旋后 parent、subR、subRL 的平衡因子分別更新為 0、1、0
（3）當 subRL 原始平衡因子是 0 時（說明 subRL為新增結點），左右雙旋后 parent、subR、subRL 的平衡因子分別更新為0、0、0
可以看到，經(jīng)過右左雙旋后，樹的高度沒有發(fā)生變化，所以右左雙旋后無需繼續(xù)往上更新平衡因子。
代碼示例
private:
// 右左雙旋（先右單旋，再左單旋）
void RotateRL(Node* parent)
{Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
// 1.先以subR為旋轉點進行右單旋
RotateR(parent->_right);
// 2.再以parent為旋轉點進行左單旋
RotateL(parent);
// 3.更新平衡因子
if (bf == 0)
{ subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{ subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{ subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else
{ // 如果走到了這里，說明subRL的平衡因子在旋轉前就有問題
assert(false);
}
}假如以 parent 為根的子樹不平衡，即 parent 的平衡因子為 2 或者 -2，分以下情況考慮
旋轉完成后，原 parent 為根的子樹個高度降低，已經(jīng)平衡，不需要再向上更新。
6. AVL樹的刪除平衡二叉樹的刪除操作與插入操作類似，先執(zhí)行標準的 BST 刪除操作（可以參考文章： 什么是二叉查找樹），然后進行相應的平衡操作。
主要是三個大思路：
只不過與二叉搜索樹的刪除不同的是，刪除節(jié)點后的平衡因子需要不斷更新，最差情況下一直要調整到根節(jié)點的位置。
下面簡單講解一下刪除的算法思想吧。
🍑 算法思想我們以刪除一個結點w為例進行說明平衡二叉樹刪除操作的具體算法步驟：
w執(zhí)行標準的二叉搜索樹的刪除操作；w開始，向上回溯，找到第一個不平衡的結點z（即平衡因子不是 -1，0 或 1 的結點），設y為結點z的高度最高的孩子結點；x是結點y的高度最高的孩子結點。z為根結點的子樹進行平衡操作，其中x、y、z可以的位置有四種情況，BST 刪除操作之后的平衡操作也就處理以下四種情況：y是z的左孩子，x是y的左孩子 （Left Left ，LL )；y是z的左孩子，x是y的右孩子 （Left Right ，LR )；y是z的右孩子，x是y的右孩子 （Right Right ，RR )；y是z的右孩子，x是y的左孩子 （Right Right ，RL )；這里的四種情況與插入操作一樣，但需要注意的是，插入操作僅需要對以z為根的子樹進行平衡操作；而平衡二叉樹的刪除操作就不一樣，先對以z為根的子樹進行平衡操作，之后可能需要對z的祖先結點進行平衡操作，向上回溯直到根結點。
我們已刪除下圖中的結點 32 為例進行說明。
第一步：由于 32 結點為葉子結點，直接刪除，并保存刪除結點的父節(jié)點 17 。
第二步：從節(jié)點 17 向上回溯，找到第一個不平衡結點 44 ，并找到不平衡結點的左右孩子中深度最深的結點 78 （即 y ）；以及 y 的孩子結點當中深度最深的結點 50 （即 x ）。 發(fā)現(xiàn)為 RL 的情況。
第三步：對結點 78 進行右旋操作
第四步：對結點 44 進行左旋操作
我們以刪除下圖中的結點 80 為例進行說明。
第一步，由于結點 80 為葉子結點，則直接刪除，并保存結點 80 的父結點 78 。
第二步：從結點 78 開始尋找第一個不平衡結點，發(fā)現(xiàn)就是結點 78 本身（即結點 z ），找到結點 78 深度最深的葉子結點 60 （即結點 y ），以及結點 y 的深度最深的葉結點 55 （即結點 x ）。即 LL 的情況。
第三步：右旋結點 78
第四步：從旋轉后的返回的新的根結點 60 向上回溯（這里就和平衡二叉樹的插入操作有別了奧，平衡二叉樹的插入操作僅對第一個不平衡結點的子樹進行平衡操作，而AVL的刪除需要不斷地回溯，直到根結點平衡為止 ），判斷是否還有不平衡結點，發(fā)現(xiàn)整棵樹的根結點 50 為第一個不平衡結點，找到對應的 y 結點 25 和 x 結點 10 。同樣是 LL 的情況。
第五步：對 z 結點 50 進行右旋操作。
關于左旋與右旋操作，以及平衡因子的計算與之前講的文章（ 什么是二叉查找樹）中的實現(xiàn)是一致的，我們直接看 AVL 樹刪除操作的實現(xiàn)代碼：
代碼示例
// 刪除函數(shù)
bool Erase(const K& key)
{//用于遍歷二叉樹
Node* parent = nullptr;
Node* cur = _root;
//用于標記實際的刪除結點及其父結點
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{ if (key< cur->_kv.first) //所給key值小于當前結點的key值
{ //往該結點的左子樹走
parent = cur;
cur = cur->_left;
}
else if (key >cur->_kv.first) //所給key值大于當前結點的key值
{ //往該結點的右子樹走
parent = cur;
cur = cur->_right;
}
else //找到了待刪除結點
{ if (cur->_left == nullptr) //待刪除結點的左子樹為空
{if (cur == _root) //待刪除結點是根結點
{_root = _root->_right; //讓根結點的右子樹作為新的根結點
if (_root)
_root->_parent = nullptr;
delete cur; //刪除原根結點
return true; //根結點無祖先結點，無需進行平衡因子的更新操作
}
else
{delParentPos = parent; //標記實際刪除結點的父結點
delPos = cur; //標記實際刪除的結點
}
break; //刪除結點有祖先結點，需更新平衡因子
}
else if (cur->_right == nullptr) //待刪除結點的右子樹為空
{if (cur == _root) //待刪除結點是根結點
{_root = _root->_left; //讓根結點的左子樹作為新的根結點
if (_root)
_root->_parent = nullptr;
delete cur; //刪除原根結點
return true; //根結點無祖先結點，無需進行平衡因子的更新操作
}
else
{delParentPos = parent; //標記實際刪除結點的父結點
delPos = cur; //標記實際刪除的結點
}
break; //刪除結點有祖先結點，需更新平衡因子
}
else //待刪除結點的左右子樹均不為空
{//替換法刪除
//尋找待刪除結點右子樹當中key值最小的結點作為實際刪除結點
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{minParent = minRight;
minRight = minRight->_left;
}
cur->_kv.first = minRight->_kv.first; //將待刪除結點的key改為minRight的key
cur->_kv.second = minRight->_kv.second; //將待刪除結點的value改為minRight的value
delParentPos = minParent; //標記實際刪除結點的父結點
delPos = minRight; //標記實際刪除的結點
break; //刪除結點有祖先結點，需更新平衡因子
}
}
}
if (delParentPos == nullptr) //delParentPos沒有被修改過，說明沒有找到待刪除結點
{ return false;
}
//記錄待刪除結點及其父結點（用于后續(xù)實際刪除）
Node* del = delPos;
Node* delP = delParentPos;
//更新平衡因子
while (delPos != _root) //最壞一路更新到根結點
{ if (delPos == delParentPos->_left) //delParentPos的左子樹高度降低
{ delParentPos->_bf++; //delParentPos的平衡因子++
}
else if (delPos == delParentPos->_right) //delParentPos的右子樹高度降低
{ delParentPos->_bf--; //delParentPos的平衡因子--
}
//判斷是否更新結束或需要進行旋轉
if (delParentPos->_bf == 0)//需要繼續(xù)往上更新平衡因子
{ //delParentPos樹的高度變化，會影響其父結點的平衡因子，需要繼續(xù)往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
}
else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新結束
{ break; //delParent樹的高度沒有發(fā)生變化，不會影響其父結點及以上結點的平衡因子
}
else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要進行旋轉（此時delParentPos樹已經(jīng)不平衡了）
{ if (delParentPos->_bf == -2)
{if (delParentPos->_left->_bf == -1)
{Node* tmp = delParentPos->_left; //記錄delParentPos右旋轉后新的根結點
RotateR(delParentPos); //右單旋
delParentPos = tmp; //更新根結點
}
else if (delParentPos->_left->_bf == 1)
{Node* tmp = delParentPos->_left->_right; //記錄delParentPos左右旋轉后新的根結點
RotateLR(delParentPos); //左右雙旋
delParentPos = tmp; //更新根結點
}
else //delParentPos->_left->_bf == 0
{Node* tmp = delParentPos->_left; //記錄delParentPos右旋轉后新的根結點
RotateR(delParentPos); //右單旋
delParentPos = tmp; //更新根結點
//平衡因子調整
delParentPos->_bf = 1;
delParentPos->_right->_bf = -1;
break; //更正
}
}
else //delParentPos->_bf == 2
{if (delParentPos->_right->_bf == -1)
{Node* tmp = delParentPos->_right->_left; //記錄delParentPos右左旋轉后新的根結點
RotateRL(delParentPos); //右左雙旋
delParentPos = tmp; //更新根結點
}
else if (delParentPos->_right->_bf == 1)
{Node* tmp = delParentPos->_right; //記錄delParentPos左旋轉后新的根結點
RotateL(delParentPos); //左單旋
delParentPos = tmp; //更新根結點
}
else //delParentPos->_right->_bf == 0
{Node* tmp = delParentPos->_right; //記錄delParentPos左旋轉后新的根結點
RotateL(delParentPos); //左單旋
delParentPos = tmp; //更新根結點
//平衡因子調整
delParentPos->_bf = -1;
delParentPos->_left->_bf = 1;
break; //更正
}
}
//delParentPos樹的高度變化，會影響其父結點的平衡因子，需要繼續(xù)往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
//break; //error
}
else
{ assert(false); //在刪除前樹的平衡因子就有問題
}
}
//進行實際刪除
if (del->_left == nullptr) //實際刪除結點的左子樹為空
{ if (del == delP->_left) //實際刪除結點是其父結點的左孩子
{ delP->_left = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
else //實際刪除結點是其父結點的右孩子
{ delP->_right = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
}
else //實際刪除結點的右子樹為空
{ if (del == delP->_left) //實際刪除結點是其父結點的左孩子
{ delP->_left = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
else //實際刪除結點是其父結點的右孩子
{ delP->_right = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
}
delete del; //實際刪除結點
return true;
}中序遍歷和二叉樹的中序實現(xiàn)一樣，只不過因為中序是遞歸遍歷，涉及到傳參，所以需要寫一個子函數(shù)。
代碼示例
private:
// 中序遍歷（子函數(shù)）
void _InOrder(Node* root)
{if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_kv.first<< " ";
_InOrder(root->_right);
}
public:
// 中序遍歷
void InOrder()
{_InOrder(_root);
cout<< endl;
}AVL樹的查找與二叉搜索樹一樣：
代碼示例
public:
// 查找函數(shù)
Node* Find(const K& key)
{Node* cur = _root;
while (cur)
{ if (cur->_kv.first< key) // key值大于該結點的值
{ cur = cur->_left; // 在該結點的右子樹當中查找
}
else if (cur->_kv.first< key) // key值小于該結點的值
{ cur = cur->_right; // 在該結點的左子樹當中查找
}
else // 當前節(jié)點的值等于key值
{ return cur; //返回該結點
}
}
return nullptr; //查找失敗
}這里和求二叉樹的深度是一樣的方式，采用分治的思想：
若為空樹，則深度為 0。
若不為空樹，則深度 = 左右子樹中深度大的值 + 1（為什么要加1呢？因為還有第一層，也就是根節(jié)點這一層！）
代碼示例
private:
// 求樹的高度（子函數(shù)）
int _Height(Node* root)
{if (root == nullptr) // 空樹高度為0
return 0;
int lh = _Height(root->_left); // 遞歸計算左子樹高度
int rh = _Height(root->_right); // 遞歸計算右子樹高度
return lh >rh ? lh + 1 : rh + 1; // 左樹高度或者右樹高度大的哪一個，然后再+1，就是整棵樹的高度
}
public:
// 樹的高度
int Height()
{return _Height(_root);
}AVL樹是在二叉搜索樹的基礎上加入了平衡性的限制，因此要驗證AVL樹，可以分為下面兩步：
（1）驗證其為二叉搜索樹
（2）驗證其為平衡樹
每個節(jié)點子樹高度差的絕對值不超過 1（注意節(jié)點中如果沒有平衡因子）
節(jié)點的平衡因子是否計算正確
檢測二叉樹是否平衡的代碼
private:
// 判斷是否為平衡二叉樹（子函數(shù)）
bool _IsBalanceTree(Node* root)
{// 空樹也是AVL樹
if (nullptr == root)
return true;
// 計算pRoot節(jié)點的平衡因子：即pRoot左右子樹的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果計算出的平衡因子與pRoot的平衡因子不相等，或者
// pRoot平衡因子的絕對值超過1，則一定不是AVL樹
if (abs(diff) >= 2)
{ cout<< root->_kv.first<< "節(jié)點平衡因子異常"<< endl;
return false;
}
if (diff != root->_bf)
{ cout<< root->_kv.first<< "節(jié)點平衡因子不符合實際"<< endl;
return false;
}
// pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
return _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}
public:
// 判斷是否為平衡二叉樹
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}（1）測試一組有序值
// 插入有序值
void TestAVLTree1()
{const int N = 20;
vectorv;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i< N; ++i)
{v.push_back(i);
}
AVLTreet;
for (auto e : v)
{t.Insert(make_pair(e, e));
}
if (t.IsBalanceTree())
{cout<< "AVL樹平衡"<< endl;
}
else
{cout<< "AVL樹不平衡"<< endl;
}
cout<< "AVL樹高度："<< t.Height()<< endl;
cout<< "中序遍歷：";
t.InOrder();
} 運行結果
（2）測試一組隨機值
// 插入隨機值
void TestAVLTree2()
{const size_t N = 20;
vectorv;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i< N; ++i)
{v.push_back(rand());
}
AVLTreet;
for (auto e : v)
{t.Insert(make_pair(e, e));
}
if (t.IsBalanceTree())
{cout<< "AVL樹平衡"<< endl;
}
else
{cout<< "AVL樹不平衡"<< endl;
}
cout<< "AVL樹高度："<< t.Height()<< endl;
cout<< "中序遍歷：";
t.InOrder();
} 運行結果
優(yōu)點：
缺點：
時間復雜度分析：
總結：
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
