一、基本概念
1.發(fā)展背景
-
普通的二叉搜索樹在極端情況下會退化成類似鏈表的形狀，從而使查找的效率降低至O(N)。
-
在此基礎(chǔ)上，蘇聯(lián)與以色列數(shù)學(xué)家
Adelson-Velskii 與 蘇聯(lián)數(shù)學(xué)家Landis，發(fā)明出了 AVL樹或者說平衡二叉搜索樹。
注：第一張——Adelson-Velskii（1922-2014） ，第二張——Landis（1921——1997）
2.性質(zhì)
- 左右子樹的高度差的絕對值不大于1
- 每個子樹都是AVL樹。
說明：這樣做的目的就是為了嚴(yán)格控制平衡，以便于提高查找效率，但是控制高度差一直為0是不可能的，至于為什么不能控制成0，假設(shè)只有兩個結(jié)點必然存在1的高度差。
二、實現(xiàn)原理
①插入操作
1.平衡因子
英文名：balance factor
- 目的：
保證左右子樹的高度差的絕對值不大于1 - 大多數(shù)的實現(xiàn)方式：
存放的是右子樹與左子樹的高度差
1.1平衡因子的更新
1.1.1樹的高度變化
① 左邊新增結(jié)點
② 右邊新增結(jié)點
- 總結(jié)
- 左邊新增，根節(jié)點的平衡因子減1
- 右邊新增，根節(jié)點的平衡因子加1
- 平衡因子從0變?yōu)?或者-1
繼續(xù)分析：
?兩種情況樹的高度增加1，也就是平衡因子從0變?yōu)?或者-1，既然高度變化了，可能會導(dǎo)致上面的樹不平衡。
如：
此時我們需要向上更新平衡因子，再根據(jù)右邊高度變化與左邊高度變化，決定根的平衡因子加1還是減1。
- 推論：
由于可能會向上更新平衡因子，那么AVL樹是三叉鏈的結(jié)構(gòu)。
如圖：
1.1.2樹的高度不變
① 左邊新增結(jié)點
② 右邊新增結(jié)點
- 同理
- 左邊新增，根節(jié)點的平衡因子減1
- 右邊新增，根節(jié)點的平衡因子加1
- 平衡因子由1或者-1變?yōu)?
繼續(xù)分析，這里的根節(jié)點的所在樹的高度即——左右子樹高度的最大值 + 1（根節(jié)點的高度）
左右子樹的高度的最大值不變，即這顆樹高度不變，即不用往上繼續(xù)更新且達(dá)到平衡。
2. 旋轉(zhuǎn)
-
說明：旋轉(zhuǎn)就是讓
不平衡的樹再次平衡的手段。 -
條件：平衡因子為2或者-2，即高度差的絕對值為2。
-
補充：若平衡因子大于等于3，說明當(dāng)前樹就不是AVL樹，需要檢驗之前的代碼。
但是我們又得對情況進行分類討論，因為不同情況讓樹再次平衡的旋轉(zhuǎn)方式不同。
2.1左旋
- 說明：也就是右邊高度高，需要旋轉(zhuǎn)來降低右邊的高度，進而達(dá)到平衡。
一步一步分析，先來個最簡單的：
此時，旋轉(zhuǎn)過后平衡因子全變?yōu)?，且當(dāng)前樹達(dá)到平衡。注意此時3結(jié)點的左結(jié)點為空！(細(xì)節(jié))
再舉一個例子：
此時，旋轉(zhuǎn)過后平衡因子1和3的平衡因子變?yōu)?，且當(dāng)前樹達(dá)到平衡，此時我們是不用管其它子樹的，因為子樹必然是AVL樹，要不然更不到根節(jié)點就停止了。
最后來一個稍微復(fù)雜的例子：
此時，旋轉(zhuǎn)過后平衡因子-5和0的平衡因子變?yōu)?，且當(dāng)前樹達(dá)到平衡。
這是具體的圖便于輔助理解，然后我們再畫出所有情況的抽象圖：
- 總結(jié)
-
只能在c部分上插入結(jié)點才可能會引發(fā)根節(jié)點左單旋,也就是說parent的右邊為cur且新增結(jié)點在cur的右邊。 - 旋轉(zhuǎn)過后
cur與parent的平衡因子變?yōu)?。
- 細(xì)節(jié)
- b的父節(jié)點連接parent時，需要判斷b部分是否為空。
- parent的父節(jié)點連接cur時，需要保存一下parent的父節(jié)點。
- 根據(jù)parent的父節(jié)點判斷是否需要修改根節(jié)點，若為空則修改，若不為空，則將cur鏈接到parent的父節(jié)點，同時更新parent父節(jié)點的指向。
- 實現(xiàn)代碼
void RotateL(Node* parent)
{
//畫圖分析：
//操作的結(jié)點有cur,cur_left,ppnode
Node* cur = parent->_right;
Node* cur_left = cur->_left;
//將parent的右節(jié)點改為cur_left
parent->_right = cur_left;
//改變cur_left父節(jié)點的轉(zhuǎn)向
//cur_left可能為空
if (cur_left != nullptr)
{
cur_left->_parent = parent;
}
//將parent鏈接在cur的左邊
//為了更新cur的parent需要保存parent的父節(jié)點
Node* ppnode = parent->_parent;
cur->_left = parent;
parent->_parent = cur;
//ppnode可能為空
if (ppnode == nullptr)
{
//需要修改根節(jié)點
_root = cur;
cur->_parent = nullptr;
}
else
{
//改變ppnode的指向
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新平衡因子
cur->_bf = parent->_bf = 0;
}
2.2右旋
說明：也就是左邊高度高，需要旋轉(zhuǎn)來降低右邊的高度，進而達(dá)到平衡。
跟左旋的分析方式一樣。
先來個簡單的感受一下：
此時，旋轉(zhuǎn)過后平衡因子parent和cur的平衡因子變?yōu)?，且當(dāng)前樹達(dá)到平衡。
再舉一個例子：
最后來一個稍微復(fù)雜的例子：
畫出所有情況的抽象圖：
- 總結(jié)
-
只能在a部分上插入結(jié)點才可能會引發(fā)根節(jié)點右單旋,也就是說parent與cur與高度變化的c樹的根節(jié)點在同一個方向且在parent的左 - 旋轉(zhuǎn)過后
cur與parent的平衡因子變?yōu)?。
- 細(xì)節(jié)——同左旋
- b的父節(jié)點連接parent時，需要判斷b部分是否為空。
- parent的父節(jié)點連接cur時，需要保存一下parent的父節(jié)點。
- 根據(jù)parent的父節(jié)點判斷是否需要修改根節(jié)點，若為空則修改，若不為空，則將cur鏈接到parent的父節(jié)點，同時更新parent父節(jié)點的指向。
- 實現(xiàn)代碼：
void RotateR(Node* parent)
{
//操作的結(jié)點
Node* cur = parent->_left;
Node* cur_right = cur->_right;
//第一步：將cur_right鏈接到parent的left
parent->_left = cur_right;
//更改cur_right的父節(jié)點
//注意：cur_right可能為空
if (cur_right != nullptr)
{
cur_right->_parent = parent;
}
//第二步：將parent鏈接到cur的右結(jié)點。
//先保存一下parent的父節(jié)點
Node* ppnode = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
//ppnode為空說明需要修改根節(jié)點
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新平衡因子
cur->_bf = parent->_bf = 0;
}
2.3右左雙旋
- 可以簡單理解為，需要進行處理的左旋。
說明：單旋無法解決問題，原因是發(fā)生了拐彎，需要用右旋講折線變?yōu)橹本€，再進行左旋。
因為情況有點多我們就來個簡單的，直接化抽象圖，看結(jié)論比較容易理解。
先來個簡單的：
先右旋之后折線變成了直線，變成了左旋的形狀，再進行左旋，最后的cur與cur_left與parent的平衡因子變成了0，最終cur_left變成了根節(jié)點。
再化抽象圖：
初始狀態(tài)
還是一樣，不過得分兩種情況進行討論：
- 新增結(jié)點在c樹上，會導(dǎo)致parent的平衡因子變?yōu)?1，cur的平衡因子變?yōu)?。
- 新增結(jié)點在b樹上，會導(dǎo)致parent的平衡因子變?yōu)?，cur的平衡因子變?yōu)?
- 不管新增結(jié)點在誰上，cur_left的平衡因子都為0。
-
看圖分析，其實不看新增結(jié)點在誰身上，兩種最終的旋轉(zhuǎn)的結(jié)果是一樣的，那我們其實只需先不看新增結(jié)點再畫圖，根據(jù)最終的結(jié)果再把新增結(jié)點添上，其實會更加直觀。
-
總結(jié)
- 新增結(jié)點在c樹上，會導(dǎo)致parent的平衡因子變?yōu)?1，cur的平衡因子變?yōu)?。
- 新增結(jié)點在b樹上，會導(dǎo)致parent的平衡因子變?yōu)?，cur的平衡因子變?yōu)?。
- cur_left為新增結(jié)點，parent與cur的結(jié)點全為0。
- 實現(xiàn)代碼：
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* cur_left = cur->_left;
//CL——CurLeft
int CL_bf = cur_left->_bf;
RotateR(cur);
RotateL(parent);
//更新平衡因子
if (CL_bf == 0)
{
cur->_bf = parent->_bf = cur_left->_bf = 0;
//雖然沒必要，但是起到了解耦的作用。
}
else if (CL_bf == 1)
{
parent->_bf = -1;
cur->_bf = cur_left->_bf = 0;
}
else if(CL_bf == -1)
{
cur->_bf = 1;
parent->_bf = cur_left->_bf = 0;
}
else
{
cout << __LINE__ << ":" << endl;
perror("平衡因子有誤");
exit(-1);
}
}
2.4 左右雙旋
- 可以理解為，需要進行處理的右旋。
說明：單旋無法解決問題，原因是發(fā)生了拐彎，需要用左旋講折線變?yōu)橹本€，再進行右旋。
分析方法跟右左雙旋一樣。
先來個簡單的：
先左旋之后折線變成了直線，變成了右旋的形狀，再進行右旋，最后的cur與cur_left與parent的平衡因子變成了0，最終cur_left變成了根節(jié)點。
再來個抽象的：
還是一樣，不過得分兩種情況進行討論：
- 新增結(jié)點在c樹上，會導(dǎo)致cur的平衡因子變?yōu)?1，parent的平衡因子變?yōu)?。
- 新增結(jié)點在b樹上，會導(dǎo)致cur的平衡因子變?yōu)?，parent的平衡因子變?yōu)?
- 不管新增結(jié)點在誰上，cur_right的平衡因子都為0。
- 總結(jié)
- cur_right平衡因子為1，說明新增結(jié)點在b樹上，會導(dǎo)致cur的平衡因子變?yōu)?，parent的平衡因子變?yōu)?。
- cur_right的平衡因子為-1，新增結(jié)點在c樹上，會導(dǎo)致cur的平衡因子變?yōu)?1，parent的平衡因子變?yōu)?。
- cur_right的平衡因子為0，cur與parent的平衡因子都變?yōu)?。
- 不管新增結(jié)點在誰上，cur_right的平衡因子都為0。
- 代碼實現(xiàn)
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* cur_right = cur->_right;
int CR_bf = cur_right->_bf;
RotateL(cur);
RotateR(parent);
if (CR_bf == 0)
{
parent->_bf = cur->_bf = cur_right->_bf = 0;
}
else if(CR_bf == 1)
{
cur->_bf = -1;
parent->_bf = cur_right->_bf = 0;
}
else if (CR_bf == -1)
{
parent->_bf = 1;
cur->_bf = cur_right->_bf = 0;
}
else
{
cout << __LINE__ << ":" << endl;
perror("平衡因子有誤");
exit(-1);
}
}
②驗證
說明：
- 根據(jù)定義驗證每顆子樹的高度差
- 需要判斷當(dāng)前的右子樹的高度差是否等于平衡因子
直接根據(jù)平衡因子進行判斷，有點監(jiān)守自盜的感覺，你能保證自己更新的平衡因子就是正確的么？我都不敢保證。
1.求二叉樹高度
- 后序遍歷
size_t Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int LHeight = Height(root->_left);
int RHeight = Height(root->_right);
return max(LHeight, RHeight) + 1;
}
2. 判斷是否為AVL樹
bool _IsAVLTree(Node* root)
{
if (root == nullptr)
{
return true;
}
int RHeight = Height(root->_right);
int LHeight = Height(root->_left);
if (abs(RHeight - LHeight) > 1 || root->_bf != RHeight - LHeight)
{
return false;
}
return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}
優(yōu)化一下：文章來源：http://www.zghlxwxcb.cn/news/detail-709144.html
bool IsAVLTree()
{
bool is_AVL = true;
_IsAVLTree(_root, is_AVL);
return is_AVL;
}
int _IsAVLTree(Node* root,bool& is_AVL)
{
if (root == nullptr)
{
return 0;
}
int RHeight = _IsAVLTree(root->_right, is_AVL);
int LHeight = _IsAVLTree(root->_left, is_AVL);
if (abs(RHeight - LHeight) > 1 || root->_bf != RHeight - LHeight)
{
is_AVL = false;
}
return max(RHeight, LHeight) + 1;
}
源碼
#include<iostream>
#include<assert.h>
using namespace std;
namespace MY_STL
{
template<class Key,class Val>
struct AVLTreeNode
{
typedef AVLTreeNode<Key, Val> Node;
AVLTreeNode(const pair<Key,Val>& key = pair<Key,Val>())
:_key(key.first)
,_val(key.second)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
Key _key;
Val _val;
//三叉鏈的結(jié)構(gòu)
Node* _left;
Node* _right;
Node* _parent;
int _bf;
};
template<class Key, class Val>
class AVLTree
{
typedef AVLTreeNode<Key, Val> Node;
public:
AVLTree()
{}
bool insert(const pair<Key,Val>& val)
{
//第一步：插入操作
//如果根節(jié)點為空
if (_root == nullptr)
{
_root = new Node(val);
return true;
}
else
{
Node* cur = _root,*parent = _root;
while (cur)
{
if (cur->_key > val.first)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_key < val.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(val);
if (parent->_key > val.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//更新新增結(jié)點的_parent
cur->_parent = parent;
//第二步：更新平衡因子
//平衡因子：
//1. 定義為右子樹的高度減去左子樹的高度
//2. 合法范圍為{-1,0,1}
//3. 新增結(jié)點在左，父節(jié)點的平衡因子減1
//4. 新增結(jié)點在右，父節(jié)點的平衡因子加1
//5. 當(dāng)父節(jié)點的平衡因子變?yōu)?——由-1變0或者1變0時，此時AVL樹的高度不變
//6. 當(dāng)父節(jié)點的平衡因子變?yōu)?或者-1，AVL子樹的高度變化，繼續(xù)向上變化。
//7. 當(dāng)父節(jié)點的平衡因子變?yōu)?或者-2時，此時需要旋轉(zhuǎn)，進行平衡
//8. 當(dāng)父節(jié)點為根節(jié)點時，此時需要結(jié)束循環(huán)。
while (cur != _root)
{
//更新平衡因子
if (parent->_left == cur)
{
//左減1
(parent->_bf)--;
}
else
{
//右加1
(parent->_bf)++;
}
//判斷平衡因子
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//對旋轉(zhuǎn)進行分類討論
//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)
//{
// RotateRL(parent);
//}
//else if (parent->_bf == -2 && cur->_bf == 1)
//{
// RotateLR(parent);
//}
if (parent->_bf == 2)
{
//左單旋
if (cur->_bf == 1)
{
RotateL(parent);
}
else
{
RotateRL(parent);
}
}
else
{
//右單旋
if (cur->_bf == -1)
{
RotateR(parent);
}
else
{
RotateLR(parent);
}
}
//旋轉(zhuǎn)完成，樹達(dá)到平衡
break;
}
}
return true;
}
}
//根據(jù)定義進行判斷
bool IsAVLTree()
{
bool is_AVL = true;
_IsAVLTree(_root, is_AVL);
return is_AVL;
//return _IsAVLTree(_root);
}
void Print()
{
_InOrder(_root);
cout << endl;
}
//根據(jù)平衡因子進行判斷
//bool IsAVLTree()
//{
// return _IsAVLTree(_root);
//}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//bool _IsAVLTree(Node* root)
//{
// if (root == nullptr)
// return true;
// if (root->_bf >= 2 || root->_bf <= -2)
// {
// return false;
// }
// else
// {
// return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
// }
//}
//bool IsAVLTree()
//{
// bool is_AVL = true;
// _IsAVLTree(_root, is_AVL);
// return is_AVL;
//}
size_t Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int LHeight = Height(root->_left);
int RHeight = Height(root->_right);
return max(LHeight, RHeight) + 1;
}
int _IsAVLTree(Node* root,bool& is_AVL)
{
if (root == nullptr)
{
return 0;
}
int RHeight = _IsAVLTree(root->_right, is_AVL);
int LHeight = _IsAVLTree(root->_left, is_AVL);
if (abs(RHeight - LHeight) > 1 || root->_bf != RHeight - LHeight)
{
is_AVL = false;
}
return max(RHeight, LHeight) + 1;
}
bool _IsAVLTree(Node* root)
{
if (root == nullptr)
{
return true;
}
int RHeight = Height(root->_right);
int LHeight = Height(root->_left);
if (abs(RHeight - LHeight) > 1 || root->_bf != RHeight - LHeight)
{
return false;
}
return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* cur_right = cur->_right;
int CR_bf = cur_right->_bf;
RotateL(cur);
RotateR(parent);
if (CR_bf == 0)
{
parent->_bf = cur->_bf = cur_right->_bf = 0;
}
else if(CR_bf == 1)
{
cur->_bf = -1;
parent->_bf = cur_right->_bf = 0;
}
else if (CR_bf == -1)
{
parent->_bf = 1;
cur->_bf = cur_right->_bf = 0;
}
else
{
cout << __LINE__ << ":" << endl;
perror("平衡因子有誤");
exit(-1);
}
}
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* cur_left = cur->_left;
//CL——CurLeft
int CL_bf = cur_left->_bf;
RotateR(cur);
RotateL(parent);
if (CL_bf == 0)
{
cur->_bf = parent->_bf = cur_left->_bf = 0;
}
else if (CL_bf == 1)
{
parent->_bf = -1;
cur->_bf = cur_left->_bf = 0;
}
else if(CL_bf == -1)
{
cur->_bf = 1;
parent->_bf = cur_left->_bf = 0;
}
else
{
cout << __LINE__ << ":" << endl;
perror("平衡因子有誤");
exit(-1);
}
}
void RotateL(Node* parent)
{
//畫圖分析：
//操作的結(jié)點有cur,cur_left,ppnode
Node* cur = parent->_right;
Node* cur_left = cur->_left;
//將parent的右節(jié)點改為cur_left
parent->_right = cur_left;
//改變cur_left父節(jié)點的轉(zhuǎn)向
//cur_left可能為空
if (cur_left != nullptr)
{
cur_left->_parent = parent;
}
//將parent鏈接在cur的左邊
//為了更新cur的parent需要保存parent的父節(jié)點
Node* ppnode = parent->_parent;
cur->_left = parent;
parent->_parent = cur;
//ppnode可能為空
if (ppnode == nullptr)
{
//需要修改根節(jié)點
_root = cur;
cur->_parent = nullptr;
}
else
{
//改變ppnode的指向
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新平衡因子
cur->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
//操作的結(jié)點
Node* cur = parent->_left;
Node* cur_right = cur->_right;
//第一步：將cur_right鏈接到parent的left
parent->_left = cur_right;
//更改cur_right的父節(jié)點
//注意：cur_right可能為空
if (cur_right != nullptr)
{
cur_right->_parent = parent;
}
//第二步：將parent鏈接到cur的右結(jié)點。
//先保存一下parent的父節(jié)點
Node* ppnode = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
//ppnode為空說明需要修改根節(jié)點
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
//更新平衡因子
cur->_bf = parent->_bf = 0;
}
Node* _root = nullptr;
};
};
總結(jié)
?AVL樹還有刪除操作，等博主有空再補充，對于AVL樹一般來說只需要弄懂一種單旋，一種雙旋，再加一些細(xì)寫處理，代碼是不難的，難就難在了分類討論+畫圖上。今天的分享就到這里了，如果感覺有所幫助，不妨點個贊鼓勵一下吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-709144.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】AVL樹的插入與驗證的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[數(shù)據(jù)結(jié)構(gòu)]-AVL樹](https://imgs.yssmx.com/Uploads/2024/02/758787-1.png)
