C++實(shí)現(xiàn)AVL樹(shù)的示例詳解
AVL 樹(shù)的概念
也許因?yàn)椴迦氲闹挡粔螂S機(jī)，也許因?yàn)榻?jīng)過(guò)某些插入或刪除操作，二叉搜索樹(shù)可能會(huì)失去平衡，甚至可能退化為單鏈表，造成搜索效率低。
AVL Tree 是一個(gè)「加上了額外平衡條件」的二叉搜索樹(shù)，其平衡條件的建立是為了確保整棵樹(shù)的深度為 O(log2N)。
AVL Tree 要求任何節(jié)點(diǎn)的左右子樹(shù)高度相差最多為 1。當(dāng)違反該規(guī)定時(shí)，就需要進(jìn)行旋轉(zhuǎn)來(lái)保證該規(guī)定。
AVL 樹(shù)的實(shí)現(xiàn)
節(jié)點(diǎn)的定義
AVL 樹(shù)節(jié)點(diǎn)的定義比一般的二叉搜索樹(shù)復(fù)雜，它需要額外一個(gè) parent 指針，方便后續(xù)旋轉(zhuǎn)。并在每個(gè)節(jié)點(diǎn)中引入平衡因子，便于判斷是否需要旋轉(zhuǎn)。
/// @brief AVL 樹(shù)節(jié)點(diǎn)結(jié)構(gòu)
/// @tparam K 節(jié)點(diǎn)的 key 值
/// @tparam V 節(jié)點(diǎn)的 value 值
template <class K, class V>
struct AVLTreeNode {
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _bf(0)
{}
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
// 左右子樹(shù)高度相同平衡因子為：0
// 左子樹(shù)高平衡因子為負(fù)
// 右子樹(shù)高平衡因子為正
int _bf;
};
接口總覽
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
Node* Find(const K& key);
bool Insert(const pair<K, V>& kv);
private:
void RotateR(Node* parent);
void RotateL(Node* parent);
void RotateLR(Node* parent);
void RotateRL(Node* parent);
private:
Node* _root = nullptr;
};
查找
AVL 樹(shù)的查找和普通的搜索二叉樹(shù)一樣：
- 若 key 值大于當(dāng)前節(jié)點(diǎn)的值，在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中查找
- 若 key 值小于當(dāng)前節(jié)點(diǎn)的值，在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中查找
- 若 key 值等于當(dāng)前節(jié)點(diǎn)的值，返回當(dāng)前節(jié)點(diǎn)的地址
- 若找到空，查找失敗，返回空指針
/// @brief 查找指定 key 值
/// @param key 要查找的 key
/// @return 找到返回節(jié)點(diǎn)的指針，沒(méi)找到返回空指針
Node* Find(const K& key) {
Node* cur = _root;
while (cur != nullptr) {
// key 值與當(dāng)前節(jié)點(diǎn)值比較
if (key > cur->_kv.first) {
cur = cur->_right;
} else if (key < cur->_kv.first) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr;
}
插入
AVL 的插入整體分為兩步：
- 按照二叉搜索樹(shù)的方式將節(jié)點(diǎn)插入
- 調(diào)整節(jié)點(diǎn)的平衡因子
平衡因子是怎么調(diào)整的？
設(shè)新插入的節(jié)點(diǎn)為 pCur，新插入節(jié)點(diǎn)的父節(jié)點(diǎn)為 pParent。在插入之前，pParent 的平衡因子有三種可能：0、-1、1。
插入分為兩種：
- pCur 插入到 pParent 的左側(cè)，將 pParent 的平衡因子減 1
- pCur 插入到 pParent 的右側(cè)，將 pParent 的平衡因子加 1
此時(shí)，pParent 的平衡因子可能有三種情況：0、正負(fù) 1、正負(fù) 2。
- 0：說(shuō)明插入之前是正負(fù) 1，插入后被調(diào)整為 0，滿足 AVL 性質(zhì)插入成功
- 正負(fù) 1：說(shuō)明插入之前是 0，插入后被調(diào)整為正負(fù) 1，此時(shí) pParent 變高，需要繼續(xù)向上更新
- 正負(fù) 2：說(shuō)明插入之前是正負(fù) 1，插入后被調(diào)整為正負(fù) 2，此時(shí)破壞了規(guī)定，需要旋轉(zhuǎn)處理
/// @brief 插入指定節(jié)點(diǎn)
/// @param kv 待插入的節(jié)點(diǎn)
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// 先找到要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
} else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
} else {
// 已經(jīng)存在，插入失敗
return false;
}
}
// 將節(jié)點(diǎn)插入
cur = new Node(kv);
if (kv.first > parent->_kv.first) {
parent->_right = cur;
cur->_parent = parent;
} else {
parent->_left = cur;
cur->_parent = parent;
}
// 更新平衡因子，直到正常
while (parent != nullptr) {
// 調(diào)整父親的平衡因子
if (parent->_left == cur) {
--parent->_bf;
} else {
++parent->_bf;
}
if (parent->_bf == 0) {
// 此時(shí)不需要再繼續(xù)調(diào)整了，直接退出
break;
} else if (parent->_bf == 1 || parent->_bf == -1) {
// 此時(shí)需要繼續(xù)向上調(diào)整
cur = parent;
parent = parent->_parent;
} else if (parent->_bf == 2 || parent->_bf == -2) {
// 此時(shí)需要旋轉(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);
}
// 旋轉(zhuǎn)完了就平衡了，直接退出
break;
} else {
// 此時(shí)說(shuō)明之前就處理錯(cuò)了
assert(false);
} // end of if (parent->_bf == 0)
} // end of while (parent != nullptr)
return true;
}
旋轉(zhuǎn)
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 X，由于節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)，因此可以分為四種情況：
- 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的左子樹(shù)——左左：右單旋
- 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的右子樹(shù)——左右：左右雙旋
- 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的右子樹(shù)——右右：左單旋
- 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的左子樹(shù)——右左：右左雙旋
右單旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent，parent 的父節(jié)點(diǎn)為 pParent，parent 的左子樹(shù)為 subL，subL 的右子樹(shù)為 subLR。
右單旋的操作流程：
- 讓 subLR 作為 parent 的左子樹(shù)
- 讓 parent 作為 subL 的右子樹(shù)
- 讓 subL 作為整個(gè)子樹(shù)的新根
- 更新平衡因子
/// @brief 進(jìn)行右單旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateR(Node* parent) {
Node* pParent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
// 更改鏈接關(guān)系
// 1. subLR 作為 parent 的左子樹(shù)
parent->_left = subLR;
if (subLR != nullptr) {
subLR->_parent = parent;
}
// 2. parent 作為 subL 的右子樹(shù)
subL->_right = parent;
parent->_parent = subL;
// 3. subL 作為整個(gè)子樹(shù)的新根
if (parent == _root) {
// parent 為 _root，此時(shí)令 subL 為 _root
_root = subL;
subL->_parent = nullptr;
} else {
// parent 不為 _root，pParent 也就不為空
if (parent == pParent->_left) {
pParent->_left = subL;
} else {
pParent->_right = subL;
}
subL->_parent = pParent;
}
// 4. 更新平衡因子
// 觀察上圖明顯可知
subL->_bf = 0;
parent->_bf = 0;
}
左單旋
左單旋與右單旋類似，只是方向不同。
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent，parent 的父節(jié)點(diǎn)為 pParent，parent 的右子樹(shù)為 subR，subR 的左子樹(shù)為 subRL。
左單旋的操作流程：
- 讓 subRL 作為 parent 的右子樹(shù)
- 讓 parent 作為 subR 的左子樹(shù)
- 讓 subR 作為整個(gè)子樹(shù)的新根
- 更新平衡因子
/// @brief 進(jìn)行左單旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateL(Node* parent) {
Node* pParetn = parent->_parent;
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
// 更改鏈接關(guān)系
// 1. subRL 作為 parent 的右子樹(shù)
parent->_right = subRL;
if (subRL != nullptr) {
subRL->_parent = parent;
}
// 2. parent 作為 subR 的左子樹(shù)
subR->_left = parent;
parent->_parent = subR;
// 3. subR 作為整個(gè)子樹(shù)的新根
if (parent == _root) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parent == pParetn->_left) {
pParetn->_left = subR;
} else {
pParetn->_right = subR;
}
subR->_parent = pParetn;
}
// 4. 更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
左右雙旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent，parent 的左子樹(shù)為 subL，subL 的右子樹(shù)為 subLR。
左右雙旋就是對(duì) subL 進(jìn)行一次左單旋，對(duì) parent 進(jìn)行一次右單旋。雙旋也就完成了，要注意的是雙旋后平衡因子的更新。
此時(shí)分三種情況：
1.新插入的節(jié)點(diǎn)是 subLR 的右子樹(shù)
2.新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù)
3.新插入的是 subLR
結(jié)合上述情況，寫出如下代碼：
/// @brief 進(jìn)行左右雙旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateLR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = parent->_left->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1) {
// 新插入節(jié)點(diǎn)是 subLR 的右子樹(shù)
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
} else if (bf == -1) {
// 新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù)
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
} else if (bf == 0) {
// 新插入的節(jié)點(diǎn)是 subLR
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
} else {
assert(false);
}
}
右左雙旋
假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent，parent 的右子樹(shù)為 subR，subR 的左子樹(shù)為 subRL。
右左雙旋就是對(duì) subR 進(jìn)行一次右單旋，對(duì) parent 進(jìn)行一次左單旋。流程和左右雙旋一樣，這里就不過(guò)多介紹了。
void RotateRL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = parent->_right->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 1) {
// 新插入節(jié)點(diǎn)是 subRL 的右子樹(shù)
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
} else if (bf == -1) {
// 新插入的節(jié)點(diǎn)是 subRL 的左子樹(shù)
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
} else if (bf == 0) {
// 新插入的節(jié)點(diǎn)是 subRL
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
} else {
assert(false);
}
}
以上就是C++實(shí)現(xiàn)AVL樹(shù)的示例詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ AVL樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
c++下使用windows api遍歷指定文件夾及其子文件夾中的文件
這篇文章主要介紹了c++下使用windows api遍歷指定文件夾及其子文件夾中的文件實(shí)現(xiàn)代碼，一般都是通過(guò)c++自帶的函數(shù)實(shí)現(xiàn)2021-07-07
???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法
這篇文章主要介紹了???????C語(yǔ)言實(shí)現(xiàn)單鏈表基本操作方法，文章圍繞主題展開(kāi)詳細(xì)介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-05-05
一步步從底層入手搞定C++引用與內(nèi)聯(lián)函數(shù)
內(nèi)聯(lián)函數(shù)是代碼插入到調(diào)用者代碼處的函數(shù),內(nèi)聯(lián)函數(shù)通過(guò)避免被調(diào)用的開(kāi)銷來(lái)提高執(zhí)行效率,下面這篇文章主要給大家介紹了關(guān)于如何從底層入手搞定C++引用與內(nèi)聯(lián)函數(shù)的相關(guān)資料,需要的朋友可以參考下2023-03-03
本文通過(guò)代碼給大家介紹c語(yǔ)言數(shù)字交換的題目，通過(guò)實(shí)例代碼給大家講解的很詳細(xì)，具有一定的參考借鑒價(jià)值，對(duì)c語(yǔ)言感興趣的朋友一起看看吧2021-08-08
C++設(shè)計(jì)模式之策略模式（Strategy）
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計(jì)模式之策略模式Strategy ，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-04-04
C++實(shí)現(xiàn)獲取IP、子網(wǎng)掩碼、網(wǎng)關(guān)、DNS等本機(jī)網(wǎng)絡(luò)參數(shù)的方法
這篇文章主要介紹了C++實(shí)現(xiàn)獲取IP、子網(wǎng)掩碼、網(wǎng)關(guān)、DNS等本機(jī)網(wǎng)絡(luò)參數(shù)的方法,需要的朋友可以參考下2014-07-07
C++線程安全容器stack和queue的使用詳細(xì)介紹
stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行 元素的插入與提取操作；隊(duì)列是一種容器適配器，專門用于在FIFO上下文(先進(jìn)先出)中操作，其中從容器一端插入元素，另一端提取元素2022-08-08
C語(yǔ)言中關(guān)于sizeof 和 strlen的區(qū)別分析
本文通過(guò)示例簡(jiǎn)單分析了4種情況下C語(yǔ)言中sizeof 和 strlen的區(qū)別，算是個(gè)人經(jīng)驗(yàn)的一個(gè)小小的總結(jié)，如有遺漏還請(qǐng)大家告知。2015-02-02
C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04
這篇文章主要介紹了C語(yǔ)言判斷回文數(shù)的小例子，有需要的朋友可以參考一下2014-01-01