C++中AVL樹的底層以及實現(xiàn)方法總結(jié)
一、AVL樹的概念
AVL樹是一種高度平衡的平衡二叉樹，相比于搜索二叉樹，它的特點在于左右子樹都為AVL樹且樹的高度差的絕對值不超過1。這里我們會引入一個新的概念叫做平衡因子。平衡因子也就是左右子樹的高度差，我們可以通過平衡因子方便我們后續(xù)去觀察和控制樹是否平衡。
二、AVL樹的性質(zhì)
AVL樹主要有三大性質(zhì)：
1.每棵樹的左右子樹都是AVL樹。
2.左子樹和右子樹的高度之差的絕對值不超過1。
3.每個節(jié)點都會有一個平衡因子，且任何一個節(jié)點的平衡因子都為1、0、-1。
三、AVL樹的實現(xiàn)
1. 樹的基本結(jié)構(gòu)
AVL樹的結(jié)點包含了左右節(jié)點的指針以及父親節(jié)點的指針，同時還有有key、value以及代表樹平衡的平衡因子。
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
//平衡因子
int _bf;
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
2. 樹的插入
樹的插入按照搜索二叉樹的規(guī)則進行插入。插入節(jié)點后更新平衡因子，如果沒有違反規(guī)則(即沒有導(dǎo)致節(jié)點的平衡因子變成2/-2)，則插入結(jié)束；如果違反規(guī)則，則樹會不平衡，需要進行旋轉(zhuǎn)操作。
平衡因子的更新規(guī)則：
1.平衡因子 = 右子樹高度 - 左子樹高度。
2.只有子樹高度的變化才會影響當(dāng)前節(jié)點的平衡因子。
3.插入節(jié)點后會增加數(shù)的高度，若新增節(jié)點在parent的右子樹，則parent的平衡因子++，相反在parent的左子樹時，則平衡因子- -。
每更新完一個節(jié)點的平衡因子都需要進行以下判斷：
1.如果parent的平衡因子等于1/-1時，說明parent原先的平衡因子為0，插入節(jié)點后左子樹或右子樹的高度增加了，說明還需要向上更新平衡因子。
2.如果parent的平衡因子等于0，說明parent原先的平衡因子為1/-1，插入節(jié)點后左右兩棵子樹從不平衡變平衡了，說明無需更新平衡因子。
3.如果parent的平衡因子等于2/-2時，說明parent原先的平衡因子等于1/-1，插入節(jié)點后插入到了較高的那一棵子樹，說明此時以parent為根節(jié)點的子樹已經(jīng)不平衡了，需要進行旋轉(zhuǎn)處理。
bool Insert(const pair<K, V>& kv)
{
//如果樹為空，則插入的節(jié)點就是根節(jié)點
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
parent->_bf++;
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//繼續(xù)往上進行更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//不平衡，旋轉(zhuǎn)處理
if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if(parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
}
else
{
assert(false);
}
break;
}
return true;
}
3. 樹的旋轉(zhuǎn)
旋轉(zhuǎn)的目的就是讓樹從失衡到平衡，降低樹的高度。旋轉(zhuǎn)主要分為四種，分別為左單旋、右單旋、左右雙旋和右左雙旋。下面我們具體講講每一種旋轉(zhuǎn)的內(nèi)部邏輯。
• 左單旋
條件：新節(jié)點插入到子樹較高的右側(cè)。
我們用圖來感受一下其旋轉(zhuǎn)的過程：
1.先將15的左子樹的節(jié)點12變成10的右子樹。
2.再將10變成15的左子樹，15成為新樹的根節(jié)點。
3.更新平衡因子
由于左單旋的情況很多，我們也可以用一張抽象圖來表示：
代碼所示：
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subR;
if (subRL)
subRL->_parent = parent;
Node* pparent = parent->_parent;
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent == parent->_right)
{
parent->_right = subR;
}
else
{
parent->_left = subR;
}
subR->_parent = pparent;
}
parent->_bf = subR->_bf = 0;
}
• 右單旋
條件：新節(jié)點插入到子樹較高的左側(cè)
用圖來感受旋轉(zhuǎn)的過程：
我們會發(fā)現(xiàn)和左單旋和相似
1.先將5的右子樹的值b變成10的左子樹。
2.再將10變成5的右子樹，旋轉(zhuǎn)完后5成為整棵樹的根節(jié)點。
3.更新平衡因子。
代碼所示：
//右單旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if(subLR)
subLR->_parent = parent;
Node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pparent == parent->_left)
{
parent->_left = subL;
}
else
{
parent->_right = subL;
}
subL->_parent = pparent;
}
parent->_bf = subL->_bf = 0;
}
• 左右雙旋
條件：新節(jié)點插入到較高左子樹的右側(cè)。
下面我們用圖來演示一下其旋轉(zhuǎn)過程：
1.插入新節(jié)點
2.以節(jié)點5為旋轉(zhuǎn)點進行左單旋
3.以節(jié)點為10進行右單旋
4.旋轉(zhuǎn)完后更新平衡因子。
平衡因子又分為三種情況：
1.當(dāng)subLR的平衡因子為-1時，左右雙旋后parent、subL,subLR的平衡因子分別為1、0、0。
2.當(dāng)subLR的平衡因子為1時，左右雙旋后parent、subL,subLR的平衡因子分別為0、-1、0。
3.當(dāng)subLR的平衡因子為0時，左右雙旋后parent、subL,subLR的平衡因子分別為0、0、0。
代碼所示：
//左右雙旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
• 右左雙旋
條件：插入到較高右子樹的左側(cè)
其旋轉(zhuǎn)過程和左右雙旋類似，這就不一一列舉了。
旋轉(zhuǎn)完過后也是需要更新平衡因子，平衡因子也是跟左右雙旋一樣有三種情況。
代碼所示：
//右左雙旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent);
RotateL(parent);
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
四、AVL樹的其它功能
1. 樹的查找
定義一個cur指針從樹的根節(jié)點開始查找，按一下規(guī)則進行查找：
1.當(dāng)key的值小于當(dāng)前節(jié)點的值時，則在該節(jié)點的左邊進行查找。
2.當(dāng)key的值大于當(dāng)前節(jié)點的值時，則在該節(jié)點的右邊進行查找。
3.若key的值等于當(dāng)前節(jié)點的值時，則說明查找成功，返回true。
4.若遍歷完還沒查找到該節(jié)點的值，則說明沒有此節(jié)點，返回false。
代碼所示：
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
2. 樹的遍歷
我們遍歷方式有前序、中序、后序、層序等方式，我們在這就采用中序遍歷的方式來遍歷樹的每一節(jié)點。
代碼所示：
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
3. 樹的高度
int _Height(Node* root)
{
if (root == nullptr)
{
return;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
4. 樹的大小
返回左子樹+右子樹再加上根節(jié)點即可。
int _Size(Node* root)
{
if (root == nullptr)
{
return;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
五、總結(jié)
1. AVL樹的優(yōu)缺點
優(yōu)點：
**1.查找效率高：**由于AVL樹總是保持平衡，其高度相對較低，因此查找操作的時間復(fù)雜度為O(log2N)，效率較高。
2.結(jié)構(gòu)穩(wěn)定： AVL樹的平衡性使得其結(jié)構(gòu)相對穩(wěn)定，不會出現(xiàn)極端不平衡的情況，從而保證了操作的穩(wěn)定性和可靠性。
缺點：
1.插入和刪除復(fù)雜： AVL樹在插入和刪除節(jié)點時，可能需要通過旋轉(zhuǎn)操作來保持樹的平衡，比較復(fù)雜。
2.可能導(dǎo)致性能下降： 在頻繁插入和刪除的場景下，AVL樹需要不斷地進行旋轉(zhuǎn)操作來保持平衡，這就有可能導(dǎo)致性能降低。
2. 完整代碼
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
// 需要parent指針，后續(xù)更新平衡因子可以看到
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
//平衡因子
int _bf; // balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
parent->_bf++;
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//繼續(xù)往上進行更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//不平衡，旋轉(zhuǎn)處理
if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if(parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
}
else
{
assert(false);
}
break;
}
return true;
}
//右單旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if(subLR)
subLR->_parent = parent;
Node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pparent == parent->_left)
{
parent->_left = subL;
}
else
{
parent->_right = subL;
}
subL->_parent = pparent;
}
parent->_bf = subL->_bf = 0;
}
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subR;
if (subRL)
subRL->_parent = parent;
Node* pparent = parent->_parent;
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent == parent->_right)
{
parent->_right = subR;
}
else
{
parent->_left = subR;
}
subR->_parent = pparent;
}
parent->_bf = subR->_bf = 0;
}
//左右雙旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
//右左雙旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent);
RotateL(parent);
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void Hight()
{
return _Hight(_root);
}
void Size()
{
return _Size(_root);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
{
return;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int _Size(Node* root)
{
if (root == nullptr)
{
return;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
private:
Node* _root = nullptr;
};總結(jié)
到此這篇關(guān)于C++中AVL樹的底層以及實現(xiàn)方法總結(jié)的文章就介紹到這了,更多相關(guān)C++ AVL樹底層及實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)猜牌小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
在C++中，decltype作為操作符，用于查詢表達式的數(shù)據(jù)類型。decltype在C++11標準制定時引入，主要是為泛型編程而設(shè)計，以解決泛型編程中，由于有些類型由模板參數(shù)決定，而難以（甚至不可能）表示之的問題。2016-03-03
這篇文章主要為大家介紹了C語言編程之thread多線程，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
C++應(yīng)用Eigen庫對應(yīng)實現(xiàn)matlab中部分函數(shù)問題
這篇文章主要介紹了C++應(yīng)用Eigen庫對應(yīng)實現(xiàn)matlab中部分函數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要為大家分享了C語言圖書借閱系統(tǒng)源碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-02-02
C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計)
這篇文章主要介紹了C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
本文詳細講解了C語言實現(xiàn)掃雷并附完整代碼，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-11-11
這篇文章主要為大家詳細介紹了C語言實現(xiàn)繪制余弦曲線的相關(guān)知識,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-01-01
C++中有左值和右值的概念，其實，左值和右值的區(qū)分也同樣適用于類對象，本文中將左值的類對象稱為左值對象，將右值的類對象稱為右值對象，對C++11?引用限定符相關(guān)知識感興趣的朋友跟隨小編一起看看吧2023-01-01
淺談C語言中的sizeof()和strlen()的區(qū)別
本文主要介紹了C語言中的sizeof()和strlen()的區(qū)別，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05