C++中平衡二叉搜索樹的模擬實(shí)現(xiàn)
更新時(shí)間：2023年09月08日 10:08:53 作者：平凡的小蘇
二叉搜索樹雖可以縮短查找的效率,但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹,查找元素相當(dāng)于在順序表中搜索元素,效率低下,所以本文給大家介紹了C++平衡二叉的搜索樹模擬實(shí)現(xiàn)方法,需要的朋友可以參考下
一、AVL樹的概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當(dāng)于在順序表中搜索元素，效率低下。
因此，有兩位科學(xué)家發(fā)明了一種方法：當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個(gè)結(jié)點(diǎn)的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
- 它的左右子樹都是AVL樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個(gè)結(jié)點(diǎn)，其高度可保持在O(log_2n)，搜索時(shí)間復(fù)雜度O(log_2n)
二、AVL樹節(jié)點(diǎn)的定義
#include <cassert>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;//該節(jié)點(diǎn)的左孩子
AVLTreeNode<K, V>* _right;//該節(jié)點(diǎn)的右孩子
AVLTreeNode<K, V>* _parent;//該節(jié)點(diǎn)是父親節(jié)點(diǎn)
int _bf;//平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};三、AVL樹的插入
AVL樹就是在二叉搜索樹的基礎(chǔ)上引入了平衡因子，因此AVL樹也可以看成是二叉搜索樹。那么AVL樹的插入過程可以分為兩步：
- 按照二叉搜索樹的方式插入新節(jié)點(diǎn)
- 調(diào)整節(jié)點(diǎn)的平衡因子
注：
- 新增節(jié)點(diǎn)如果在左邊的話，平衡因子需要_bf–；
- 新增節(jié)點(diǎn)如果在右邊，平衡因子需要_bf++;
- 更新后parent平衡因子==0，說明parent所在的子樹高度不變，不會(huì)再影響祖先，不用再沿著到root的路徑上進(jìn)行更新
- 更新后parent的平衡因子==1 or -1，說明parent所在的左右子樹的高度變化，會(huì)影響祖先，需要繼續(xù)沿著root的路徑上往上更新
- 更新后parent的phenomena因子==2 or -2，說明parent所在的子樹的高度變化且不平衡對parent所在子樹進(jìn)行旋轉(zhuǎn)，讓它平衡
- 更新根節(jié)點(diǎn)
而樹的旋轉(zhuǎn)需要分為四種情況：左單旋轉(zhuǎn)、右單旋轉(zhuǎn)、左右雙旋、右左雙旋
1.AVL樹的右單旋轉(zhuǎn)
- 新節(jié)點(diǎn)插入較高左子樹的左側(cè)—左左：右單旋
上圖在插入前，AVL樹是平衡的，新節(jié)點(diǎn)插入到30的左子樹(注意：此處不是左孩子)中，30左子樹增加了一層，導(dǎo)致以60為根的二叉樹不平衡，要讓60平衡，只能將60左子樹的高度減少一層，右子樹增加一層，即將左子樹往上提，這樣60轉(zhuǎn)下來，因?yàn)?0比30大，只能將其放在30的右子樹，而如果30有右子樹，右子樹根的值一定大于30，小于60，只能將其放在60的左子樹，旋轉(zhuǎn)完成后，更新節(jié)點(diǎn)的平衡因子即可。在旋轉(zhuǎn)過程中，有以下幾種情況需要考慮：
- 30節(jié)點(diǎn)的右孩子可能存在，也可能不存在
- 60可能是根節(jié)點(diǎn)，也可能是子樹
- 如果是根節(jié)點(diǎn)，旋轉(zhuǎn)完成后，要更新根節(jié)點(diǎn)
- 如果是子樹，可能是某個(gè)節(jié)點(diǎn)的左子樹，也可能是右子樹
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curRight = cur->_right;
parent->_left = curRight;
cur->_right = parent;
Node* ppNode = parent->_parent;
if (curRight)//右孩子可能存在，也可能不存在，所以需要判斷，需要在parent改變前判斷
{
curRight->_parent = parent;
}
parent->_parent = cur;
if (parent == _root)//parent可能是根節(jié)點(diǎn)，也可能不是根節(jié)點(diǎn)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = cur;
}
else
{
ppNode->_right = cur;
}
cur->_parent = ppNode;
}
cur->_bf = parent->_bf = 0;//將平衡因子調(diào)整
}2.AVL樹的左單旋轉(zhuǎn)
- 新節(jié)點(diǎn)插入較高右子樹的右側(cè)—右右：左單旋
這里進(jìn)行參考右單旋轉(zhuǎn)就可理解
注：如果是左單旋轉(zhuǎn)parent的平衡因子應(yīng)該是2，cur的平衡因子應(yīng)該是1如果是右單旋轉(zhuǎn)parent的平衡因子應(yīng)該是-2，cur的平衡因子應(yīng)該是-1。
3.AVL樹的先左單旋再右單旋
- 新節(jié)點(diǎn)插入較高左子樹的右側(cè)—左右：先左單旋再右單旋
即：先對30進(jìn)行左單旋，然后再對90進(jìn)行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。
注：平衡因子的更新分為三種情況
1.當(dāng)h是為0的時(shí)候，進(jìn)行左右雙旋，那么它的平衡因子都是為0的。
2.當(dāng)h>0的時(shí)候，進(jìn)行左右雙旋，那么它的平衡因子修改分為兩種情況
(1)當(dāng)插入節(jié)點(diǎn)在b的位置，如圖所示，30節(jié)點(diǎn)的平衡因子修改為0，60節(jié)點(diǎn)的平衡因子修改為090節(jié)點(diǎn)的平衡因子修改為1
(2)當(dāng)擦汗如節(jié)點(diǎn)在c的位置，將上圖的紫色方框放到c的位置，那么60和90節(jié)點(diǎn)的平衡因子為0，30節(jié)點(diǎn)的平衡因子為-1.這個(gè)平衡因子的修改是根據(jù)目錄AVL樹的定義的方式修改的。
具體代碼：
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curRight = cur->_right;
int bf = curRight->_bf;
//復(fù)用左單旋轉(zhuǎn)和右單旋轉(zhuǎn)
RotateL(cur);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curRight->_bf = 0;
}
else if (bf == -1)//curRight的左樹插入新節(jié)點(diǎn)
{
parent->_bf = 1;
cur->_bf = 0;
curRight->_bf = 0;
}
else if (bf == 1)//curRight的右樹插入新節(jié)點(diǎn)
{
cur->_bf = -1;
parent->_bf = 0;
curRight->_bf = 0;
}
else//不可能出現(xiàn)此情況，如果出現(xiàn)就是出錯(cuò)
{
assert(false);
}
}4.AVL樹的先右單旋再左單旋
- 新節(jié)點(diǎn)插入較高右子樹的左側(cè)—右左：先右單旋再左單旋
參考左右雙旋。具體代碼如下：
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
//復(fù)用右單旋轉(zhuǎn)和左單旋轉(zhuǎn)
RotateR(cur);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)//curLeft的右樹插入新節(jié)點(diǎn)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if(bf == -1)//curLeft的左樹插入新節(jié)點(diǎn)
{
cur->_bf = 1;
parent->_bf = 0;
curleft->_bf = 0;
}
else
{
assert(false);
}
}四、AVL樹代碼的驗(yàn)證
int TreeHight(Node* root)
{
if (root == nullptr)
return 0;
int leftHight = TreeHight(root->_left);
int rightHight = TreeHight(root->_right);
return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
void Inorder()
{
_Inorder(_root);
}
bool IsBalance()
{
return _IsBalance(_root);
}五、AVL樹的刪除（略）
按照二叉搜索樹的方式對平衡二叉樹節(jié)點(diǎn)進(jìn)行刪除。更新平衡因子時(shí)，平衡因子為1或-1便可以停止向上更新。
當(dāng)平衡因子絕對值大于1時(shí)，同樣需要進(jìn)行旋轉(zhuǎn)解決。
六、AVL樹的整體代碼
#include <iostream>
#include <cassert>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;//該節(jié)點(diǎn)的左孩子
AVLTreeNode<K, V>* _right;//該節(jié)點(diǎn)的右孩子
AVLTreeNode<K, V>* _parent;//該節(jié)點(diǎn)是父親節(jié)點(diǎn)
int _bf;//平衡因子
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* cur = _root;
Node* parent = nullptr;
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 // if (cur == parent->_right)
{
parent->_bf++;
}
if (parent->_bf == 0)
{
// 更新結(jié)束
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)//左單旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//右單旋
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//右左雙旋
{
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)//左右雙旋
{
RotateLR(parent);
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curRight = cur->_right;
int bf = curRight->_bf;
//復(fù)用左單旋轉(zhuǎn)和右單旋轉(zhuǎn)
RotateL(cur);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curRight->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curRight->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = -1;
parent->_bf = 0;
curRight->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
//復(fù)用右單旋轉(zhuǎn)和左單旋轉(zhuǎn)
RotateR(cur);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if(bf == -1)
{
cur->_bf = 1;
parent->_bf = 0;
curleft->_bf = 0;
}
else
{
assert(false);
}
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curRight = cur->_right;
parent->_left = curRight;
cur->_right = parent;
Node* ppNode = parent->_parent;
if (curRight)
{
curRight->_parent = parent;
}
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = cur;
}
else
{
ppNode->_right = cur;
}
cur->_parent = ppNode;
}
cur->_bf = parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft)//判斷是否為空，空的話就不用接上父親節(jié)點(diǎn)
{
curleft->_parent = parent;
}
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
parent->_bf = cur->_bf = 0;
}
int TreeHight(Node* root)
{
if (root == nullptr)
return 0;
int leftHight = TreeHight(root->_left);
int rightHight = TreeHight(root->_right);
return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
void Inorder()
{
_Inorder(_root);
}
bool IsBalance()
{
return _IsBalance(_root);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftHight = TreeHight(root->_left);
int rightHight = TreeHight(root->_right);
//檢查平衡因子對不對
if (rightHight - leftHight != root->_bf)
{
cout << "平衡因子出現(xiàn)異常" << endl;
return false;
}
//需要遞歸檢查是否平衡
return (leftHight - rightHight <= 1 && leftHight - rightHight >= -1)
&& _IsBalance(root->_left) && _IsBalance(root->_right);
}
private:
Node* _root = nullptr;
};測試代碼：
#include "9.7AVLtree.h"
int main()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//AVLTree<int, int> t;
//for (auto e : a)
//{
// t.Insert(make_pair(e, e));
//}
//
// t.Inorder();
//
// cout << t.IsBalance() << endl;
srand((unsigned int)time(0));
const size_t N = 10000;
AVLTree<int, int> t;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand();
t.Insert(make_pair(x, x));
//cout << t.IsBalance() << endl;
}
t.Inorder();
cout << t.IsBalance() << endl;
return 0;
}以上就是C++中平衡二叉搜索樹的模擬實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++平衡二叉搜索樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C++從匯編的視角看對象的創(chuàng)建,從匯編的視角來看，調(diào)用構(gòu)造器和調(diào)用 “返回對象” 的函數(shù)是一樣的，從匯編的角度來看，對象就是一堆數(shù)據(jù)的排列，比如說最普通的對象就是數(shù)據(jù)成員按照聲明順序直接排列，需要的朋友可以參考下2022-01-01
這篇文章主要為大家詳細(xì)介紹了C++的類與對象，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C++11的新特性--可變模版參數(shù)（variadic templates）是C++11新增的最強(qiáng)大的特性之一,它對參數(shù)進(jìn)行了高度泛化，它能表示0到任意個(gè)數(shù)、任意類型的參數(shù),這篇文章主要給大家詳細(xì)介紹了關(guān)于c++11增加的變參數(shù)模板的相關(guān)資料,需要的朋友可以參考下2021-08-08
深入理解約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法
本篇文章是對約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
QPainter是Qt的一個(gè)繪圖類,它的主要任務(wù)是在繪圖設(shè)備上進(jìn)行2D圖形渲染,本文主要介紹了Qt?QPainter的使用方法,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03
VisualStudio2022編寫C語言的實(shí)現(xiàn)步驟
VisualStudio2022是一款強(qiáng)大的集成開發(fā)環(huán)境,可以用來編寫C語言程序,本文主要介紹了VisualStudio2022編寫C語言的實(shí)現(xiàn)步驟,具有一定的參考價(jià)值,感興趣的可以了解一下2024-06-06
這篇文章主要介紹了C++11新特性std::make_tuple的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
這篇文章主要為大家詳細(xì)介紹了C/C++中不定參數(shù)的使用的相關(guān)知識,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12
這篇文章主要介紹了基于C語言實(shí)現(xiàn)的迷宮游戲代碼,對于學(xué)習(xí)游戲開發(fā)的朋友相信有一定的借鑒價(jià)值,需要的朋友可以參考下2014-08-08
C語言實(shí)現(xiàn)動(dòng)態(tài)開辟存儲楊輝三角
這篇文章主要介紹了如何利用C語言實(shí)現(xiàn)動(dòng)態(tài)開辟存儲楊輝三角，可以靈活的開辟空間，充分的利用空間。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以參考一下2022-03-03