一、前言
二、AVL樹(shù)的性質(zhì)
三、AVL樹(shù)節(jié)點(diǎn)的定義
四、AVL樹(shù)的插入
五、AVL樹(shù)的平衡調(diào)整
六、AVL樹(shù)的驗(yàn)證
6.1 驗(yàn)證有序
6.2 驗(yàn)證平衡
七、AVL樹(shù)的刪除
八、AVL樹(shù)的性能和代碼
一、前言
還沒(méi)有學(xué)習(xí)過(guò)二叉搜索樹(shù)的同學(xué)可以移步
【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹(shù)-CSDN博客https://blog.csdn.net/Eristic0618/article/details/137919573?spm=1001.2014.3001.5501AVL樹(shù)，又稱為平衡二叉樹(shù)，它基于二叉搜索樹(shù)并通過(guò)平衡而得到。
在前面的學(xué)習(xí)中我們提到，二叉搜索樹(shù)可以提高搜索數(shù)據(jù)的效率，但在數(shù)據(jù)有序的情況下會(huì)退化為單支樹(shù)，此時(shí)在樹(shù)中查找元素就得遍歷一整個(gè)分支，時(shí)間復(fù)雜度也會(huì)退化至O(N)。
如果有一種算法，可以使二叉搜索樹(shù)時(shí)刻保持左右子樹(shù)的平衡，就可以避免這種最壞情況。
因此，兩位俄羅斯的數(shù)學(xué)家G.M.Adelson-Velskii和E.M.Landis在1962年發(fā)明了AVL樹(shù)，解決了上述問(wèn)題。
二、AVL樹(shù)的性質(zhì)
當(dāng)我們向二叉搜索樹(shù)中插入新節(jié)點(diǎn)時(shí)，如果能用某種方法時(shí)刻保證樹(shù)中每個(gè)節(jié)點(diǎn)的左右子樹(shù)高度之差不超過(guò)1，就可以降低整棵樹(shù)的高度，保證每條分支的平衡
AVL樹(shù)的性質(zhì)如下：
- AVL樹(shù)可以是空樹(shù)
- 一顆AVL樹(shù)的左右子樹(shù)都是AVL樹(shù)
- 一顆AVL樹(shù)的左右子樹(shù)高度差不超過(guò)1
例如：
三、AVL樹(shù)節(jié)點(diǎn)的定義
AVL樹(shù)的左右子樹(shù)高度差不能超過(guò)1，但是如何便捷的去檢測(cè)該性質(zhì)是否被打破呢？
我們可以在節(jié)點(diǎn)中定義一個(gè)平衡因子，如果左子樹(shù)比右子樹(shù)高一層，那么平衡因子就為-1；如果左右子樹(shù)一樣高，平衡因子就為0；如果右子樹(shù)比左子樹(shù)高一層，那么平衡因子就為1，這三種情況下AVL樹(shù)的性質(zhì)都沒(méi)有被打破。
按照這個(gè)規(guī)則，如果平衡因子為-2、2或其他值，則說(shuō)明左右子樹(shù)已經(jīng)失衡，性質(zhì)被打破。
在調(diào)整失衡的AVL樹(shù)時(shí)，我們需要頻繁的訪問(wèn)父節(jié)點(diǎn)，所以在AVL樹(shù)中我們需要使用三叉鏈，因此AVL樹(shù)的節(jié)點(diǎn)除了包含左右子節(jié)點(diǎn)的指針，還需要一個(gè)指向父節(jié)點(diǎn)的指針
另外需要說(shuō)明一下，本文中，我們使用key/value模型的AVL樹(shù)
AVL樹(shù)節(jié)點(diǎn)的定義如下：
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv; //第一個(gè)數(shù)據(jù)存儲(chǔ)key，第二個(gè)數(shù)據(jù)存儲(chǔ)value
int _bf; //平衡因子(balance factor)
AVLTreeNode(const pair<const K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0) //新節(jié)點(diǎn)左右都為空，平衡因子為0
{}
};可能有些同學(xué)對(duì)pair沒(méi)有了解，這里簡(jiǎn)單介紹一下
pair可以將兩個(gè)數(shù)據(jù)組成一組元素，因此對(duì)于key/value模型這種需要用到兩個(gè)數(shù)據(jù)為一組的元素時(shí)就可以使用，內(nèi)部的成員變量為first和second，其主要使用方法為：
pair<T1, T2> p1(v1, v2); //輸入兩個(gè)數(shù)據(jù)創(chuàng)建pair類型變量
make_pair(v1, v2); //輸入兩個(gè)數(shù)據(jù)通過(guò)函數(shù)創(chuàng)建pair類型變量
p1.first //訪問(wèn)p1的第一個(gè)數(shù)據(jù)
p1.second //訪問(wèn)p1的第二個(gè)數(shù)據(jù)四、AVL樹(shù)的插入
向AVL樹(shù)中插入節(jié)點(diǎn)與向二叉搜索樹(shù)中插入節(jié)點(diǎn)的過(guò)程基本相同，唯一的區(qū)別就是AVL樹(shù)在插入節(jié)點(diǎn)后可能存在失衡的情況，需要調(diào)整。
我們先按照二叉搜索樹(shù)的規(guī)則將節(jié)點(diǎn)插入到AVL樹(shù)中，并判斷插入的節(jié)點(diǎn)在父節(jié)點(diǎn)的左邊還是右邊
按照平衡因子的規(guī)則，如果新節(jié)點(diǎn)插入到了父節(jié)點(diǎn)的左側(cè)，那么父節(jié)點(diǎn)的平衡因子-1
如果新節(jié)點(diǎn)插入到了父節(jié)點(diǎn)的右側(cè)，那么父節(jié)點(diǎn)的平衡因子+1
以上，便是新增節(jié)點(diǎn)的父節(jié)點(diǎn)平衡因子可能的變化情況。
但是！插入一個(gè)節(jié)點(diǎn)不但會(huì)影響父節(jié)點(diǎn)，還可能會(huì)影響到祖先節(jié)點(diǎn)。
我們觀察上面的四種可能，其中左邊的兩種情況下，插入節(jié)點(diǎn)后以父節(jié)點(diǎn)為根的子樹(shù)高度發(fā)生了變化；在右邊的兩種情況下，插入節(jié)點(diǎn)后以父節(jié)點(diǎn)為根的子樹(shù)高度沒(méi)有發(fā)生變化。
觀察過(guò)后可以發(fā)現(xiàn)，當(dāng)父節(jié)點(diǎn)的平衡因子從0變?yōu)?/-1后，子樹(shù)高度發(fā)生變化；當(dāng)父節(jié)點(diǎn)的平衡因子從1/-1變?yōu)?后，子樹(shù)高度不發(fā)生變化?
如果以父節(jié)點(diǎn)為根的子樹(shù)高度沒(méi)有發(fā)生變化，那么就不會(huì)影響到祖先節(jié)點(diǎn)的平衡因子；如果高度變了就會(huì)繼續(xù)向上影響到祖先節(jié)點(diǎn)的平衡因子
因此，我們可以通過(guò)判斷節(jié)點(diǎn)的插入位置來(lái)計(jì)算父節(jié)點(diǎn)的平衡因子，進(jìn)而判斷子樹(shù)高度是否發(fā)生變化，再進(jìn)一步計(jì)算對(duì)祖先節(jié)點(diǎn)平衡因子的影響，來(lái)判斷AVL樹(shù)是否失衡。
至此，我們已經(jīng)可以開(kāi)始寫插入新節(jié)點(diǎn)和更新平衡因子的代碼了：
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const pair<const K, V>& kv)
{
if (_root == nullptr) //檢測(cè)為空樹(shù)的情況
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) //搜索新節(jié)點(diǎn)的插入位置
{
parent = cur;
if (kv.first > cur->_kv.first)
cur = cur->_right;
else if (kv.first < cur->_kv.first)
cur = cur->_left;
else
return false;
}
cur = new Node(kv);
//將父節(jié)點(diǎn)與新節(jié)點(diǎn)鏈接
//比較新節(jié)點(diǎn)和父節(jié)點(diǎn)的key判斷插入到左邊還是右邊
if (kv.first > parent->_kv.first) //這里防止有人看不懂再?gòu)?qiáng)調(diào)一遍，kv是pair類型的對(duì)象，kv.first是key，kv.second是value
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (cur != _root)
{
//插入節(jié)點(diǎn)后除了對(duì)父節(jié)點(diǎn)造成影響還可能對(duì)祖宗節(jié)點(diǎn)造成影響
//因此隨著循環(huán)進(jìn)行，這里的cur不一定為新節(jié)點(diǎn)，可以理解為高度發(fā)生變化的子樹(shù)的根節(jié)點(diǎn)
//更新父節(jié)點(diǎn)的平衡因子
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
//更新后檢測(cè)父節(jié)點(diǎn)的平衡因子
if (parent->_bf == 0) //平衡因子為0說(shuō)明沒(méi)有打破性質(zhì)，跳出循環(huán)
break;
else if (parent->_bf == 1 || parent->_bf == -1) //更新后平衡因子為1或-1說(shuō)明高度發(fā)生變化，改變cur和parent的指向后繼續(xù)向上更新
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) //更新后平衡因子為2或-2.說(shuō)明已經(jīng)失衡，需要調(diào)整
{
//不同情況的調(diào)整方法...
if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
//...
}
else if (cur->_bf == -1)
{
//...
}
}
else
{
if (cur->_bf == 1)
{
//...
}
else if (cur->_bf == -1)
{
//...
}
}
break;
}
else //平衡因子出現(xiàn)意外情況，報(bào)錯(cuò)
{
assert(false);
}
}
return true;
}
private:
Node* _root = nullptr;
};五、AVL樹(shù)的平衡調(diào)整（附動(dòng)圖）
如果在一顆原本平衡的AVL樹(shù)中插入一個(gè)新節(jié)點(diǎn)，可能會(huì)造成失衡，此時(shí)需要調(diào)整樹(shù)的結(jié)構(gòu)使之重新平衡，這種調(diào)整方法稱為旋轉(zhuǎn)。
根據(jù)樹(shù)的原本結(jié)構(gòu)和節(jié)點(diǎn)插入位置的不同分為四種情況和四種旋轉(zhuǎn)方式：
（1）新節(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)：右單旋
自己做的動(dòng)圖大家有需要自取~這里就不加水印了
問(wèn)題來(lái)了：如何判斷插入的新節(jié)點(diǎn)的方位呢？
很簡(jiǎn)單，以上面的情況為例，插入新節(jié)點(diǎn)后60的平衡因子變成-2，說(shuō)明左子樹(shù)更高，而30的平衡因子變成-1，說(shuō)明新節(jié)點(diǎn)插入到了30的左子樹(shù)。后面左單旋以及雙旋中都同理，我們使用平衡因子就可以判斷新節(jié)點(diǎn)插入的位置
右單旋代碼如下：
void RotateRight(Node *parent) //parent為平衡因子發(fā)生失衡的節(jié)點(diǎn)
{
Node *subL = parent->_left; //subL為parent的左子節(jié)點(diǎn)
Node *subLR = subL->_right; //subLR為subL的右子節(jié)點(diǎn)
//parent，subL和subLR三個(gè)節(jié)點(diǎn)是旋轉(zhuǎn)中唯三需要進(jìn)行操作的三個(gè)節(jié)點(diǎn)
// 將parent與subLR節(jié)點(diǎn)進(jìn)行鏈接
parent->_left = subLR;
if (subLR) //subLR可能為空
subLR->_parent = parent;
Node *parentParent = parent->_parent; //記錄parent的父節(jié)點(diǎn)
if (parent != _root)
{
subL->_parent = parentParent; //將subL與parent的父節(jié)點(diǎn)鏈接
if (parent == parentParent->_left)
parentParent->_left = subL;
else
parentParent->_right = subL;
}
else //如果parent為根，旋轉(zhuǎn)后subL成為新的根
{
_root = subL;
subL->_parent = nullptr;
}
//將subL與parent鏈接
subL->_right = parent;
parent->_parent = subL;
parent->_bf = subL->_bf = 0; //更新平衡因子
}（2）新節(jié)點(diǎn)插入較高右子樹(shù)的右側(cè)：左單旋
因?yàn)樽髥涡脑砗陀覇涡穷愃频?，只要理解了右單旋，加上?dòng)圖的配合，左單旋和后面的雙旋都是很好理解的?
左單旋代碼如下：
void RotateLeft(Node *parent)
{
Node *subR = parent->_right;
Node *subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node *parentParent = parent->_parent;
if (parent != _root)
{
subR->_parent = parentParent;
if (parent == parentParent->_left)
parentParent->_left = subR;
else
parentParent->_right = subR;
}
else
{
_root = subR;
subR->_parent = nullptr;
}
subR->_left = parent;
parent->_parent = subR;
parent->_bf = subR->_bf = 0;
}（3）新節(jié)點(diǎn)插入較高左子樹(shù)的右側(cè)：先左單旋再右單旋（左右雙旋）?
這種情況又可以分為兩種情況：
不過(guò)這兩種情況都屬于在較高左子樹(shù)的右側(cè)插入，處理方式都是相同的，唯一的區(qū)別在于最后旋轉(zhuǎn)完成后，更新平衡因子時(shí)的值不同。
接下來(lái)我們以上面的那個(gè)情況為例展示左右雙旋的過(guò)程：
而下面的情況和上面的情況唯一的區(qū)別在于，最后更新的平衡因子不同
如何去決定每個(gè)節(jié)點(diǎn)更新后的平衡因子呢？可以看到這兩種情況中，如果在b下面插入新節(jié)點(diǎn)，那么旋轉(zhuǎn)過(guò)后30和60的平衡因子更新成0，90的平衡因子更新成1；如果在c下面插入新節(jié)點(diǎn)，則是60和90的平衡因子更新成0，30的平衡因子更新成-1
而新節(jié)點(diǎn)究竟插入到了b下面還是在c下面，我們可以通過(guò)插入節(jié)點(diǎn)后60的平衡因子來(lái)判斷
左右雙旋代碼如下：
void RotateLR(Node *parent)
{
Node *subL = parent->_left;
Node *subLR = subL->_right;
int bf = subLR->_bf; //記錄插入節(jié)點(diǎn)后subLR的平衡因子
RotateLeft(subL); //先左單旋
RotateRight(parent); //再右單旋
//更新平衡因子
//通過(guò)前面記錄的平衡因子判斷更新的情況
if (bf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
subL->_bf = -1;
parent->_bf = subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else
{
assert(false);
}
}（4）新節(jié)點(diǎn)插入較高右子樹(shù)的左側(cè)：先右單旋再左單旋（右左雙旋）
這種情況和左右雙旋的情況原理一樣，我們直接上動(dòng)圖和代碼
右左雙旋的代碼如下：
void RotateRL(Node *parent)
{
Node *subR = parent->_right;
Node *subRL = subR->_left;
int bf = subRL->_bf;
RotateRight(subR);
RotateLeft(parent);
if (bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 1;
parent->_bf = subRL->_bf = 0;
}
else
{
assert(false);
}
}現(xiàn)在四個(gè)旋轉(zhuǎn)的函數(shù)都實(shí)現(xiàn)了，完整的插入函數(shù)代碼如下：
bool insert(const pair<const K, V> &kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node *parent = nullptr;
Node *cur = _root;
while (cur)
{
parent = cur;
if (kv.first > cur->_kv.first)
cur = cur->_right;
else if (kv.first < cur->_kv.first)
cur = cur->_left;
else
return false;
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (cur != _root)
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
if (parent->_bf == 2) //說(shuō)明右子樹(shù)更高
{
if (cur->_bf == 1) //說(shuō)明新節(jié)點(diǎn)插入到了右邊，符合在更高右子樹(shù)的右側(cè)插入的情況
{
RotateLeft(parent); //執(zhí)行左單旋
}
else if (cur->_bf == -1) //說(shuō)明新節(jié)點(diǎn)插入到了左邊，符合在更高右子樹(shù)的左側(cè)插入的情況
{
RotateRL(parent); //執(zhí)行右左雙旋
}
}
else //左子樹(shù)更高
{
if (cur->_bf == 1) //說(shuō)明新節(jié)點(diǎn)插入到了右邊，符合在更高左子樹(shù)的右側(cè)插入的情況
{
RotateLR(parent); //執(zhí)行左右雙旋
}
else if (cur->_bf == -1) //說(shuō)明新節(jié)點(diǎn)插入到了左邊，符合在更高左子樹(shù)的左側(cè)插入的情況
{
RotateRight(parent); //執(zhí)行右單旋
}
}
break;
}
else
{
assert(false);
}
}
return true;
}六、AVL樹(shù)的驗(yàn)證
6.1 驗(yàn)證有序
最重要的插入節(jié)點(diǎn)部分完成了，不過(guò)在驗(yàn)證是否符合AVL樹(shù)性質(zhì)前，我們首先需要驗(yàn)證其是否是一棵二叉搜索樹(shù)
在之前講解二叉搜索樹(shù)中提到過(guò)，如果中序遍歷能夠得到一個(gè)有序的序列，就說(shuō)明是二叉搜索樹(shù)
中序遍歷代碼如下：
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node *root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " "; // key/value模型，我們只打印key即可
_InOrder(root->_right);
}驗(yàn)證：
說(shuō)明符合二叉搜索樹(shù)性質(zhì)
6.2 驗(yàn)證平衡
要驗(yàn)證是否符合AVL樹(shù)性質(zhì)，只需要檢測(cè)它的所有節(jié)點(diǎn)的子樹(shù)高度差不超過(guò)1即可
需要注意的是，這里不可以直接通過(guò)判斷平衡因子的絕對(duì)值是否大于1來(lái)驗(yàn)證平衡，因?yàn)槠胶庖蜃邮遣豢陀^的，可以被修改
因此，我們通過(guò)遞歸來(lái)得到每棵子樹(shù)的高度并進(jìn)行判斷即可
代碼如下：
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node *root)
{
if (root == nullptr)
return true;
int leftHeigit = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (rightHeight - leftHeigit != root->_bf)
{
cout << root->_kv.first << "平衡因子異常" << endl;
return false;
}
return abs(rightHeight - leftHeigit) <= 1
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
int Height()
{
return _Height(_root);
}
int _Height(Node *root)
{
if (root == nullptr)
return 0;
int higher = max(_Height(root->_left), _Height(root->_right));
return higher + 1;
}驗(yàn)證：
如果在驗(yàn)證是否是AVL樹(shù)中需要更多大量的測(cè)試用例，我們可以取一些隨機(jī)數(shù)：
int main()
{
const int N = 1000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (int i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
AVLTree<int, int> t;
for (auto i : v)
{
t.insert(make_pair(i, 1));
}
t.InOrder();
if (t.IsBalance())
cout << "是AVL樹(shù)" << endl;
else
cout << "不是AVL樹(shù)" << endl;
return 0;
}?
七、AVL樹(shù)的刪除
AVL樹(shù)的刪除并不是本文的重點(diǎn)，因?yàn)槠湓砦覀冊(cè)谇懊嬉呀?jīng)學(xué)習(xí)過(guò)了
我們只需要按照二叉搜索樹(shù)的方式來(lái)對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行刪除，再判斷是否失衡，如果失衡則旋轉(zhuǎn)即可
八、AVL樹(shù)的性能和代碼
AVL樹(shù)追求的是嚴(yán)格平衡，因此可以保證查找時(shí)高效的時(shí)間復(fù)雜度O(logN)，但是如果我們需要頻繁的對(duì)其進(jìn)行旋轉(zhuǎn)來(lái)維護(hù)平衡，一定程度上會(huì)影響效率，尤其是刪除節(jié)點(diǎn)時(shí)的最差情況下我們可能需要一路旋轉(zhuǎn)到根的位置。
相對(duì)于AVL樹(shù)的嚴(yán)格平衡，紅黑樹(shù)則追求一種相對(duì)平衡，因此會(huì)略勝一籌，后面的文章中會(huì)對(duì)紅黑樹(shù)進(jìn)行講解。
AVL樹(shù)的完整代碼如下：
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<const 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:
bool insert(const pair<const K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (kv.first > cur->_kv.first)
cur = cur->_right;
else if (kv.first < cur->_kv.first)
cur = cur->_left;
else
return false;
}
cur = new Node(kv);
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (cur != _root)
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//平衡異常
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateLeft(parent);
}
else if (cur->_bf == -1)
{
RotateRL(parent);
}
}
else
{
if (cur->_bf == 1)
{
RotateLR(parent);
}
else if (cur->_bf == -1)
{
RotateRight(parent);
}
}
break;
}
else
{
assert(false);
}
}
return true;
}
void RotateLeft(Node* parent) //新節(jié)點(diǎn)插入較高右子樹(shù)的右側(cè)：左單旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if(subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
if (parent != _root)
{
subR->_parent = parentParent;
if (parent == parentParent->_left)
parentParent->_left = subR;
else
parentParent->_right = subR;
}
else
{
_root = subR;
subR->_parent = nullptr;
}
subR->_left = parent;
parent->_parent = subR;
parent->_bf = subR->_bf = 0;
}
void RotateRight(Node* parent) //新節(jié)點(diǎn)插入較高左子樹(shù)的左側(cè)：右單旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
if (parent != _root)
{
subL->_parent = parentParent;
if (parent == parentParent->_left)
parentParent->_left = subL;
else
parentParent->_right = subL;
}
else
{
_root = subL;
subL->_parent = nullptr;
}
subL->_right = parent;
parent->_parent = subL;
parent->_bf = subL->_bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateRight(subR);
RotateLeft(parent);
if (bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 1;
parent->_bf = subRL->_bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateLeft(subL);
RotateRight(parent);
if (bf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
subL->_bf = -1;
parent->_bf = subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else
{
assert(false);
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
return _IsBalance(_root);
}
int Height()
{
return _Height(_root);
}
size_t Size()
{
return _Size(_root);
}
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
return cur;
}
return nullptr;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftHeigit = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (rightHeight - leftHeigit != root->_bf)
{
cout << root->_kv.first << "平衡因子異常" << endl;
return false;
}
return abs(rightHeight - leftHeigit) <= 1
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int higher = max(_Height(root->_left), _Height(root->_right));
return higher + 1;
}
size_t _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
private:
Node* _root = nullptr;
};
如果有錯(cuò)誤的地方，歡迎在評(píng)論區(qū)指出文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-857789.html
完.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-857789.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】AVL樹(shù)（萬(wàn)字超詳細(xì) 附動(dòng)圖）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-AVL樹(shù)](https://imgs.yssmx.com/Uploads/2024/02/758787-1.png)
