C++?AVL樹插入新節(jié)點后的四種調(diào)整情況梳理介紹
更新時間：2022年08月26日 10:32:02 作者：小小酥誒
AVL樹是高度平衡的而二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,本文主要給大家介紹了C++如何實現(xiàn)AVL樹,需要的朋友可以參考下
AVL樹是一個高度平衡的二叉搜索樹
- 滿足二叉搜索樹的所有特性。
- 左子樹和右子樹的高度之差的絕對值不大于1。
此處AVL樹結(jié)點的定義
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樹的定義及默認構(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é)點變成根結(jié)點
_root = new Node(kv);
return true;
}
//找到一個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;
}
}雖然插入之后，依舊會保持二叉搜索樹的特性，但是AVL樹的特性可能就被破壞了。當(dāng)平衡因子的絕對值是2的時候就需要進行調(diào)整。以下是AVL樹特性被破壞的四種情況及解決辦法：
情況一：右單旋。
結(jié)點插入后，導(dǎo)致左子樹高度比右子樹高2，其左孩子的左子樹比右子樹高1。
口訣：自己左高2，左孩子左高1，左單旋。
情況二：左單旋。
結(jié)點插入后，導(dǎo)致右子樹的高度比左子樹高2，其右孩子的右子樹比左子樹高1.
口訣：自己右高2，右孩子右高1，右單旋。
情況三：先左單旋、再右邊單旋。
結(jié)點插入后，導(dǎo)致左子樹的高度比右子樹的高度高2，其左孩子的右子樹比左子樹高度高1.
口訣：自己左高2，左孩子右高1，先右旋后左旋。
情況四：先右單旋，再左單旋。
結(jié)點插入后右子樹比左子樹高2，其右孩子的左子樹比右子樹高1。
口訣：自己右高2，右孩子左高1，先右旋后左旋。
情況三和情況四種，每一種情況又衍生出了兩種子問題，關(guān)乎平衡因子的更新數(shù)值。（假設(shè)此時平衡因子是-2的結(jié)點為parent， parent的左孩子為subL， subL的右孩子為subLR）
情況三的子問題
a、增加結(jié)點放在subLR的左子樹。
b、增加結(jié)點放在subLR的右子樹
調(diào)整后
- parent的平衡因子：1
- subL的平衡因子：0
- subLR的平衡因子：0
調(diào)整后
- parent的平衡因子：0
- subL 的平衡因子：-1
- subLR的平衡因子：0
可以看出，平衡因子的數(shù)值和結(jié)點放置位置是強相關(guān)的。雖然是同一種大情況，但是放在左子樹和放在右子樹，上面結(jié)點的平衡因子數(shù)值不一樣。情況四也有兩種子情況，和情況三的兩種子情況一樣。
假設(shè)此時平衡因子是2的結(jié)點為parent， parent的右孩子為subR， subR的左孩子為subRL
情況四的子問題
a、增加結(jié)點放在subRL的左子樹。
- parent的平衡因子：0
- subR 的平衡因子：0
- subRL的平衡因子：1
b、增加結(jié)點放在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é)點變成根結(jié)點
_root = new Node(kv);
return true;
}
//找到一個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;
}
//更新平衡因子，平衡因子不符合時，調(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ào)整情況梳理介紹的文章就介紹到這了,更多相關(guān)C++ AVL樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt實現(xiàn)SqlRelationalTable關(guān)聯(lián)表組件
在Qt中我們可以通過拖拽的方式將不同組件放到指定的位置,實現(xiàn)圖形化開發(fā)極大的方便了開發(fā)效率,本章將重點介紹SqlRelationalTable關(guān)聯(lián)表組件的常用方法及靈活運用,感興趣的可以了解一下2023-12-12
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴展的一些C++程序庫的總稱2022-11-11
C++11的新特性--可變模版參數(shù)（variadic templates）是C++11新增的最強大的特性之一,它對參數(shù)進行了高度泛化，它能表示0到任意個數(shù)、任意類型的參數(shù),這篇文章主要給大家詳細介紹了關(guān)于c++11增加的變參數(shù)模板的相關(guān)資料,需要的朋友可以參考下2021-08-08
priority_queue即優(yōu)先級隊列,它的使用場景很多,它底層是用大小根堆實現(xiàn)的,可以用log(n)的時間動態(tài)地維護數(shù)據(jù)的有序性,這篇文章主要介紹了c++ priority_queue用法入門超詳細教程,需要的朋友可以參考下2023-12-12
大家好，本篇文章主要講的是C++中構(gòu)造函數(shù)詳解，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
這篇文章主要為大家詳細介紹了QT實現(xiàn)簡單五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
本篇文章主要介紹了C++中四種加密算法之DES源代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。2016-11-11
本篇文章主要介紹了C語言WinSock學(xué)習(xí)筆記，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2007-12-12
指令系統(tǒng)的每一條指令都有一個操作符,它表示該指令應(yīng)進行什么樣性質(zhì)的操作,不同的指令用操作符這個字段的不同編碼來表示,每個編碼代表一種指令,這篇文章主要給大家介紹了關(guān)于C語言中操作符的相關(guān)資料,需要的朋友可以參考下2021-08-08
C++ 數(shù)據(jù)結(jié)構(gòu)之對稱矩陣及稀疏矩陣的壓縮存儲
這篇文章主要介紹了C++ 數(shù)據(jù)結(jié)構(gòu)之對稱矩陣及稀疏矩陣的壓縮存儲的相關(guān)資料,這里實現(xiàn)稀疏矩陣和對稱矩陣的壓縮存儲的實例，需要的朋友可以參考下2017-08-08