C++?AVL樹插入新節(jié)點(diǎn)后的四種調(diào)整情況梳理介紹
更新時(shí)間：2022年08月26日 10:32:02 作者：小小酥誒
AVL樹是高度平衡的而二叉樹,它的特點(diǎn)是AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1,本文主要給大家介紹了C++如何實(shí)現(xiàn)AVL樹,需要的朋友可以參考下
AVL樹是一個(gè)高度平衡的二叉搜索樹
- 滿足二叉搜索樹的所有特性。
- 左子樹和右子樹的高度之差的絕對值不大于1。
此處AVL樹結(jié)點(diǎn)的定義
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V> _left;
AVLTreeNode<K, V> _right;
AVLTreeNode<K, V> _parent;
pair<K, V> _kv;
int _bf; //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
使用平衡因子，是維持AVL樹的方法之一。
此處平衡因子 = 右子樹高度 - 左子樹高度。
AVL樹的定義及默認(rèn)構(gòu)造函數(shù)
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
private:
Node* _root;
};
按照普通二叉搜索樹的辦法先嘗試插入： bool insert(const pair<K, V>& kv);。
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
//插入之前是一棵空樹，則插入結(jié)點(diǎn)變成根結(jié)點(diǎn)
_root = new Node(kv);
return true;
}
//找到一個(gè)NULL位置插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//說明已經(jīng)有了，就不再插入
return false;
}
}
//已找到，準(zhǔn)備插入
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
//如果比parent小，鏈接到parent的左
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
}雖然插入之后，依舊會(huì)保持二叉搜索樹的特性，但是AVL樹的特性可能就被破壞了。當(dāng)平衡因子的絕對值是2的時(shí)候就需要進(jìn)行調(diào)整。以下是AVL樹特性被破壞的四種情況及解決辦法：
情況一：右單旋。
結(jié)點(diǎn)插入后，導(dǎo)致左子樹高度比右子樹高2，其左孩子的左子樹比右子樹高1。
口訣：自己左高2，左孩子左高1，左單旋。
情況二：左單旋。
結(jié)點(diǎn)插入后，導(dǎo)致右子樹的高度比左子樹高2，其右孩子的右子樹比左子樹高1.
口訣：自己右高2，右孩子右高1，右單旋。
情況三：先左單旋、再右邊單旋。
結(jié)點(diǎn)插入后，導(dǎo)致左子樹的高度比右子樹的高度高2，其左孩子的右子樹比左子樹高度高1.
口訣：自己左高2，左孩子右高1，先右旋后左旋。
情況四：先右單旋，再左單旋。
結(jié)點(diǎn)插入后右子樹比左子樹高2，其右孩子的左子樹比右子樹高1。
口訣：自己右高2，右孩子左高1，先右旋后左旋。
情況三和情況四種，每一種情況又衍生出了兩種子問題，關(guān)乎平衡因子的更新數(shù)值。（假設(shè)此時(shí)平衡因子是-2的結(jié)點(diǎn)為parent， parent的左孩子為subL， subL的右孩子為subLR）
情況三的子問題
a、增加結(jié)點(diǎn)放在subLR的左子樹。
b、增加結(jié)點(diǎn)放在subLR的右子樹
調(diào)整后
- parent的平衡因子：1
- subL的平衡因子：0
- subLR的平衡因子：0
調(diào)整后
- parent的平衡因子：0
- subL 的平衡因子：-1
- subLR的平衡因子：0
可以看出，平衡因子的數(shù)值和結(jié)點(diǎn)放置位置是強(qiáng)相關(guān)的。雖然是同一種大情況，但是放在左子樹和放在右子樹，上面結(jié)點(diǎn)的平衡因子數(shù)值不一樣。情況四也有兩種子情況，和情況三的兩種子情況一樣。
假設(shè)此時(shí)平衡因子是2的結(jié)點(diǎn)為parent， parent的右孩子為subR， subR的左孩子為subRL
情況四的子問題
a、增加結(jié)點(diǎn)放在subRL的左子樹。
- parent的平衡因子：0
- subR 的平衡因子：0
- subRL的平衡因子：1
b、增加結(jié)點(diǎn)放在sub的右子樹。
- parent的平衡因子：-1
- subR 的平衡因子：0
- subRL的平衡因子：0
AVL樹簡單模擬插入的對應(yīng)代碼
namespace Blog
{
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V> _left;
AVLTreeNode<K, V> _right;
AVLTreeNode<K, V> _parent;
pair<K, V> _kv;
int _bf; //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(nullptr)
{}
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
//插入之前是一棵空樹，則插入結(jié)點(diǎn)變成根結(jié)點(diǎn)
_root = new Node(kv);
return true;
}
//找到一個(gè)NULL位置插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
//說明已經(jīng)有了，就不再插入
return false;
}
}
//已找到，準(zhǔn)備插入
cur = new Node(kv);
if (parent->_kv.first > kv.first)
{
//如果比parent小，鏈接到parent的左
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//更新平衡因子，平衡因子不符合時(shí)，調(diào)節(jié)樹
while (parent)
{
//第一步：更新平衡因子
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;
//檢查平衡因子，如果平衡因子不符合，需要調(diào)整樹
if (0 == parent->_bf)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//繼續(xù)往上更新平衡因子
cur = parent;
parent = cur->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
//平衡因子不符合，說明左子樹和右子樹高度之差為2，需要調(diào)整樹
//情況一：右單旋
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
{
//說明插入之前，這顆樹就已經(jīng)不符合AVL樹的特性了
assert(false);
}
}
return true;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subLR->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
if (parentParent->_left = parent)
{
parentParent->_left = subL;
subL->_parent = parentParent;
}
else
{
parentParent->_right = subL;
subL->_parent = parentParent;
}
}
//調(diào)節(jié)后，重新更新平衡因子
parent->_bf = subL->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subRL->_left;
parent->_right = subRL;
if (subRL)
suRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (parentParent->_left = parent)
{
parentParent->_left = subR;
subR->_parent = parentParent;
}
else
{
parentParent->_right = subR;
subR->_parent = parentParent;
}
}
subR->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; //用于后面判斷加在subRL的左子樹還是右子樹
RotateL(parent->_left);
RotateR(parent);
//它的兩種子情況，更新的平衡因子不一樣
if (bf == -1)
{
//加在subLR的左子樹
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
//加在右子樹
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subL->_left;
int bf = subRL->_bf; //用于后面判斷加在subRL的左子樹還是右子樹
RotateL(parent->_right);
RotateR(parent);
//它的兩種子情況，更新的平衡因子不一樣
if (bf == -1)
{
//加在subRL的子樹
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 1;
}
else if (bf == 1)
{
//加在左子樹
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root;
};
}到此這篇關(guān)于C++ AVL樹插入新節(jié)點(diǎn)后的四種調(diào)整情況梳理介紹的文章就介紹到這了,更多相關(guān)C++ AVL樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章介紹了C++ Prim算法、優(yōu)先隊(duì)列，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
詳解NSString 與C++ string字符串的互轉(zhuǎn)
這篇文章主要介紹了詳解NSString 與C++ string字符串的互轉(zhuǎn)的相關(guān)資料,需要的朋友可以參考下2017-07-07
本篇文章對c語言的隨機(jī)函數(shù)進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下2013-05-05
C語言實(shí)現(xiàn)為無聲avi視頻添加wave音樂
這篇文章主要為大家詳細(xì)介紹了C語言如何實(shí)現(xiàn)為無聲avi視頻添加wave音樂,文中的示例代碼講解詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴可以了解一下2023-11-11
C語言可以干大事,這篇文章主要為大家詳細(xì)介紹了如何基于C語言可以完成一個(gè)簡易的Web服務(wù)器,希望這篇文章會(huì)幫你你對C語言有更深入的理解2024-03-03
這篇文章主要介紹了貪吃蛇游戲C++命令行版實(shí)例代碼,包含了常見的循環(huán)語句及相關(guān)游戲規(guī)則的判定方法,有助于更好的理解游戲設(shè)計(jì)原理,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)萬年歷小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
這篇文章主要介紹了C++ bitset用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
這篇文章主要為大家詳細(xì)介紹了Qt編寫秒表功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
關(guān)于vs strcpy_s（）和strcat_s()用法探究
這篇文章主要介紹了關(guān)于vs strcpy_s（）strcat_s()用法,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05