C++中平衡二叉搜索樹的模擬實現(xiàn)
更新時間：2023年09月08日 10:08:53 作者：平凡的小蘇
二叉搜索樹雖可以縮短查找的效率,但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹,查找元素相當于在順序表中搜索元素,效率低下,所以本文給大家介紹了C++平衡二叉的搜索樹模擬實現(xiàn)方法,需要的朋友可以參考下
一、AVL樹的概念
二叉搜索樹雖可以縮短查找的效率，但如果數(shù)據(jù)有序或接近有序二叉搜索樹將退化為單支樹，查找元素相當于在順序表中搜索元素，效率低下。
因此，有兩位科學(xué)家發(fā)明了一種方法：當向二叉搜索樹中插入新結(jié)點后，如果能保證每個結(jié)點的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點進行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。
一棵AVL樹或者是空樹，或者是具有以下性質(zhì)的二叉搜索樹：
- 它的左右子樹都是AVL樹
- 左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1)
如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結(jié)點，其高度可保持在O(log_2n)，搜索時間復(fù)雜度O(log_2n)
二、AVL樹節(jié)點的定義
#include <cassert>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;//該節(jié)點的左孩子
AVLTreeNode<K, V>* _right;//該節(jié)點的右孩子
AVLTreeNode<K, V>* _parent;//該節(jié)點是父親節(jié)點
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ào)整節(jié)點的平衡因子
注：
- 新增節(jié)點如果在左邊的話，平衡因子需要_bf–；
- 新增節(jié)點如果在右邊，平衡因子需要_bf++;
- 更新后parent平衡因子==0，說明parent所在的子樹高度不變，不會再影響祖先，不用再沿著到root的路徑上進行更新
- 更新后parent的平衡因子==1 or -1，說明parent所在的左右子樹的高度變化，會影響祖先，需要繼續(xù)沿著root的路徑上往上更新
- 更新后parent的phenomena因子==2 or -2，說明parent所在的子樹的高度變化且不平衡對parent所在子樹進行旋轉(zhuǎn)，讓它平衡
- 更新根節(jié)點
而樹的旋轉(zhuǎn)需要分為四種情況：左單旋轉(zhuǎn)、右單旋轉(zhuǎn)、左右雙旋、右左雙旋
1.AVL樹的右單旋轉(zhuǎn)
- 新節(jié)點插入較高左子樹的左側(cè)—左左：右單旋
上圖在插入前，AVL樹是平衡的，新節(jié)點插入到30的左子樹(注意：此處不是左孩子)中，30左子樹增加了一層，導(dǎo)致以60為根的二叉樹不平衡，要讓60平衡，只能將60左子樹的高度減少一層，右子樹增加一層，即將左子樹往上提，這樣60轉(zhuǎn)下來，因為60比30大，只能將其放在30的右子樹，而如果30有右子樹，右子樹根的值一定大于30，小于60，只能將其放在60的左子樹，旋轉(zhuǎn)完成后，更新節(jié)點的平衡因子即可。在旋轉(zhuǎn)過程中，有以下幾種情況需要考慮：
- 30節(jié)點的右孩子可能存在，也可能不存在
- 60可能是根節(jié)點，也可能是子樹
- 如果是根節(jié)點，旋轉(zhuǎn)完成后，要更新根節(jié)點
- 如果是子樹，可能是某個節(jié)點的左子樹，也可能是右子樹
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é)點，也可能不是根節(jié)點
{
_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é)點插入較高右子樹的右側(cè)—右右：左單旋
這里進行參考右單旋轉(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é)點插入較高左子樹的右側(cè)—左右：先左單旋再右單旋
即：先對30進行左單旋，然后再對90進行右單旋，旋轉(zhuǎn)完成后再考慮平衡因子的更新。
注：平衡因子的更新分為三種情況
1.當h是為0的時候，進行左右雙旋，那么它的平衡因子都是為0的。
2.當h>0的時候，進行左右雙旋，那么它的平衡因子修改分為兩種情況
(1)當插入節(jié)點在b的位置，如圖所示，30節(jié)點的平衡因子修改為0，60節(jié)點的平衡因子修改為090節(jié)點的平衡因子修改為1
(2)當擦汗如節(jié)點在c的位置，將上圖的紫色方框放到c的位置，那么60和90節(jié)點的平衡因子為0，30節(jié)點的平衡因子為-1.這個平衡因子的修改是根據(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é)點
{
parent->_bf = 1;
cur->_bf = 0;
curRight->_bf = 0;
}
else if (bf == 1)//curRight的右樹插入新節(jié)點
{
cur->_bf = -1;
parent->_bf = 0;
curRight->_bf = 0;
}
else//不可能出現(xiàn)此情況，如果出現(xiàn)就是出錯
{
assert(false);
}
}4.AVL樹的先右單旋再左單旋
- 新節(jié)點插入較高右子樹的左側(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é)點
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if(bf == -1)//curLeft的左樹插入新節(jié)點
{
cur->_bf = 1;
parent->_bf = 0;
curleft->_bf = 0;
}
else
{
assert(false);
}
}四、AVL樹代碼的驗證
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é)點進行刪除。更新平衡因子時，平衡因子為1或-1便可以停止向上更新。
當平衡因子絕對值大于1時，同樣需要進行旋轉(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é)點的左孩子
AVLTreeNode<K, V>* _right;//該節(jié)點的右孩子
AVLTreeNode<K, V>* _parent;//該節(jié)點是父親節(jié)點
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é)點
{
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++中平衡二叉搜索樹的模擬實現(xiàn)的詳細內(nèi)容，更多關(guān)于C++平衡二叉搜索樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
chrono是C++11中新加入的時間日期操作庫，可以方便地進行時間日期操作，本文詳細的介紹了一下如何使用，感興趣的可以了解一下2022-01-01
這篇文章主要為大家詳細介紹了C++實現(xiàn)快捷店會員管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊列
本篇文章是C語言編程篇，主要為大家介紹C語言編程中的數(shù)據(jù)結(jié)構(gòu)，詳細的講解了數(shù)據(jù)結(jié)構(gòu)的棧和隊列有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09
這篇文章主要介紹了C語言中二級指針的實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家掌握理解二級指針的知識，需要的朋友可以參考下2017-10-10
今天小編就為大家分享一篇關(guān)于C++關(guān)于Makefile的詳解含通用模板，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了基于C++實現(xiàn)的線程休眠代碼,包括了Linux平臺及基于boost庫的兩種實現(xiàn)方法,有不錯的參考借鑒價值,需要的朋友可以參考下2014-10-10
c++ 連接兩個字符串實現(xiàn)代碼 實現(xiàn)類似strcat功能
c++ 連接兩個字符串實現(xiàn)代碼 實現(xiàn)類似strcat功能，需要的朋友可以參考下2012-05-05
C++面向?qū)ο笾鄳B(tài)的實現(xiàn)和應(yīng)用詳解
相信大家都知道面向?qū)ο蟮娜筇匦允欠庋b,繼承和多態(tài)，下面這篇文章主要給大家介紹了關(guān)于C++面向?qū)ο笾鄳B(tài)的實現(xiàn)和應(yīng)用的相關(guān)資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面來一起看看吧。2017-09-09
本文主要介紹了C++中的線程同步機制淺析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-11-11
最近在使用中,發(fā)現(xiàn)了一種以前沒學(xué)過的using用法,于是在這里,將using的幾種用法總結(jié)一下,下面這篇文章主要給大家介紹了關(guān)于C++中using的三種用法,需要的朋友可以參考下2023-02-02