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