目錄
原理
平衡因子
AVL樹的插入insert
1. 新節(jié)點插入較高左子樹的左側(cè)---左左：右單旋
2.新節(jié)點插入較高右子樹的右側(cè)---右右：左單旋
新節(jié)點插入較高左子樹的右側(cè)---左右：先左單旋再右單旋
?新節(jié)點插入較高右子樹的左側(cè)---右左：先右單旋再左單旋?編輯
原理
AVL 樹是一種平衡搜索二叉樹，得名于其發(fā)明者的名字（ Adelson-Velskii 以及 Landis）。（可見名字長的好處，命名都能多占一個字母出來）。在搜索樹的前提下平衡搜索二叉樹還定義如下：
- 左右子樹的高度差小于等于 1。
- 其每一個子樹均為平衡二叉樹。
我們以SGI版本AVL樹
先來查看樹中每個結(jié)點內(nèi)容。
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode* _left;//左子樹
AVLTreeNode* _right;//右子樹
AVLTreeNode* _parent;//父節(jié)點
pair<K, V> _kv;//數(shù)據(jù)存儲內(nèi)容
int _bf;//平衡因子
AVLTreeNode(pair<K, V>kv=pair<K, V>())//默認賦值構(gòu)造
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_bf(0)
{}
};左子樹與右子樹指針我們不做過多介紹。
我們存儲AVL樹是一種存儲key_value數(shù)據(jù)的樹，所以我們使用pair庫中類型存儲數(shù)據(jù)。
讓我們看看平衡因子是什么：
平衡因子
某個結(jié)點的右子樹的高度減去左子樹的高度得到的差值。
平衡因子在[-1,1]之間都是屬于平衡的平衡搜索二叉樹，每個結(jié)點都需要符合這個要求
在插入的過程中我們會破壞平衡，這個時候就需要對樹結(jié)點進行轉(zhuǎn)至操作。
AVL樹的插入insert
和普通搜索二叉樹一樣，先要尋找插入的位置。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* parent = nullptr;//保存上級指針，我們鏈接都是cur走到空指針創(chuàng)建結(jié)點給cur
//但是這個新的結(jié)點需要被鏈接到樹中，我們不可以對
//nullptr進行訪問上級的數(shù)據(jù)，所以我們必須留一個parent
//用來鏈接新的結(jié)點。
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;//新數(shù)據(jù)小于當前數(shù)據(jù)，向cur的左邊走
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;//新數(shù)據(jù)大于當前數(shù)據(jù)，向cur的右邊走
}
else
{
return false;//數(shù)據(jù)相同退出，并返回false
}
}
cur = new Node(kv);//cur到了nullptr，創(chuàng)建新的結(jié)點。
//新結(jié)點鏈接到樹
if (parent->_kv.first <cur->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//處理新結(jié)點的_parent插入結(jié)點后我們需要修改平衡因子，確保插入數(shù)據(jù)后我們的樹依舊是AVL樹。
?更新平衡因子規(guī)則:
- ?新增在右，parent->bf+ +;新增在左，parent->bf--;
- 更新后，parent->bf == 1 or -1，說明parent插入前的平衡因子是0，說明左右子樹高度相等，插入后有一邊高，parent高度變了，該節(jié)點插入稍稍改變平衡，需要繼續(xù)往上更新平衡因子。
- 重新后，parent->bf == 0說parent插入前的平衡因子是1 or -1，說明左右子樹一邊高一邊低，插入后兩邊一樣高，插入填上了矮了那邊，parent所在子樹高度不變，不需要繼續(xù)往上更新
- 更新后，parent->bf == 2 or -2，說明parent插入前的平衡因子是1 or -1，已經(jīng)平衡臨界值，插入變成2 or -2，打破平衡，parent所在子樹需要旋轉(zhuǎn)處理
- 更新后，parent->bf > 2 r< -2的值，不可能，如果存在，則說明插入前就不是AVL樹，需要去檢查之前操作的問題，不需要再去考慮現(xiàn)在代碼的問題了。
while (parent)
{
if (parent->_right == cur)//根結(jié)點(praent)的右子樹(cur)插入了一個結(jié)點當前根結(jié)點平衡因子++
{
++parent->_bf;
}
else /*if() 可以不寫這個*///根結(jié)點(praent)的左子樹(cur)插入了一個結(jié)點當前根結(jié)點平衡因子--
{
--parent->_bf;
}
if (parent->_bf == 0)//修改更新平衡因子后，查看當前平衡因子，為0代表根補齊了該根的低子樹
//parent所在子樹高度不變，不需要繼續(xù)往上更新
{
break;
}
else if (abs(parent->_bf) == 1)//parent原本為0的平衡因子被改變，高度變高了，parent左右被
//該節(jié)點插入稍稍改變平衡，需要繼續(xù)往上更新平衡因子。
{
cur = parent;
parent = parent->_parent;
}
else if (abs(parent->_bf) == 2)//說明parent插入前的平衡因子是1 or -1，已經(jīng)平衡臨界值，插
//入變成2 or -2，打破平衡，parent所在子樹需要旋轉(zhuǎn)處理
{
//平衡被破壞。
}
else
{
std::cout << "AVL fail\n";
assert(false);
}
}?這既是轉(zhuǎn)至：
但是不平衡的情況有無數(shù)種。
?我們向大佬學習，得出4個旋轉(zhuǎn)大規(guī)律：
1. 新節(jié)點插入較高左子樹的左側(cè)---左左：右單旋
h為子樹高度。
當cur->bf==-1&&parent==-2是發(fā)生右單旋。
左左的意思是插入數(shù)據(jù)在parent的左子樹的左子樹上。
右單旋：以60結(jié)點為中心，向右旋轉(zhuǎn)AVL樹，允許h=0；
觀察圖像，我們發(fā)現(xiàn)就是改變鏈接關(guān)系，
?這里有2個小細節(jié)點，
- b允許為空，所以b的parent操作前需要判斷b是否為nullptr
- 如果60就是整棵AVL樹的根就需要改變root指向30，并且將30的parent置空
在旋轉(zhuǎn)結(jié)束以后將cur與parent結(jié)點的bf置為0
完整代碼：
void RotateR(Node* parent)
{
Node* subL = parent->_right;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (_root == parent)
{
_root = subL;
subL->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
subL->_bf = 0;
parent->_bf = 0;
}2.新節(jié)點插入較高右子樹的右側(cè)---右右：左單旋
原理與右單旋一樣。
查看代碼
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
subR->_bf = 0;
parent->_bf = 0;
}新節(jié)點插入較高左子樹的右側(cè)---左右：先左單旋再右單旋
什么意思呢？就是插入到了parent->left->right子樹上
?如果這樣的情況只用右單旋。會發(fā)生什么呢？
該破壞平衡依舊破壞平衡，用左旋就是I變2一樣的。
所以這時候我們需要左右旋一起用。
我們將30結(jié)點的右子樹再一次拆分->40根結(jié)點+左右子樹。
我們需要先以30結(jié)點左旋該子樹。
?在根據(jù)60結(jié)點做右旋旋轉(zhuǎn)，我們把40的左子樹看成一個整體
?然后重新定義40、60、30的平衡因子。
這里我們定義平衡因子又有講究，我們要觀察插入后旋轉(zhuǎn)前40結(jié)點的平衡因子。
三種情況：
旋轉(zhuǎn)前40->bf==1時，在旋轉(zhuǎn)完畢后30->bf=-1、60->bf=0、40->bf=0；
旋轉(zhuǎn)前40->bf==-1時，在旋轉(zhuǎn)完畢后30->bf=0、60->bf=1、40->bf=0；
?還有一種特殊的情況40->bf==0;30->bf=0、60->bf=0、40->bf=0；
左右旋代碼代碼：
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf==-1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
assert(false);
}
}?新節(jié)點插入較高右子樹的左側(cè)---右左：先右單旋再左單旋
?重新賦值bf與左右：先左單旋再右單旋規(guī)則一樣
旋轉(zhuǎn)前40->bf==-1時，在旋轉(zhuǎn)完畢后30->bf=0、30->bf=1、40->bf=0；
?旋轉(zhuǎn)前40->bf==1時，在旋轉(zhuǎn)完畢后30->bf=-1、30->bf=0、40->bf=0；
??旋轉(zhuǎn)前40->bf==0時，在旋轉(zhuǎn)完畢后30->bf=-1、30->bf=0、40->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)
{
parent = -1;
subR = 0;
}
else if(bf==-1)
{
parent = 0;
subR = 1;
}
else if (bf == 0)
{
parent = 0;
subR = 0;
}
else
{
assert(0);
}
}?AVLinsert完整代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-491502.html
template<class K, class V>
struct AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first <cur->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent)
{
if (parent->_right == cur)
{
++parent->_bf;
}
else
{
--parent->_bf;
}
if (parent->_bf == 0)
{
break;
}
else if (abs(parent->_bf) == 1)
{
cur = parent;
parent = parent->_parent;
}
else if (abs(parent->_bf) == 2)
{
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
break;
}
else
{
std::cout << "AVL fail\n";
assert(false);
}
}
return true;
}
}
private:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf==-1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
printf("bf is fail!!\n");
assert(false);
}
}
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)
{
parent = -1;
subR = 0;
}
else if(bf==-1)
{
parent = 0;
subR = 1;
}
else if (bf == 0)
{
parent = 0;
subR = 0;
}
else
{
printf("bf is fail!!\n");
assert(false);
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
subR->_bf = 0;
parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_right;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (_root == parent)
{
_root = subL;
subL->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
subL->_bf = 0;
parent->_bf = 0;
}
Node* _root;
};
}?謝謝！！文章來源地址http://www.zghlxwxcb.cn/news/detail-491502.html
到了這里，關(guān)于AVL樹原理以及插入代碼講解（插入操作畫圖~細節(jié)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
