C++數(shù)據(jù)結(jié)構(gòu)之AVL樹的實現(xiàn)
更新時間：2022年06月09日 14:31:28 作者：賣寂寞的小男孩
AVL樹是高度平衡的而二叉樹,它的特點是AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1,本文主要給大家介紹了C++如何實現(xiàn)AVL樹,需要的朋友可以參考下
1.概念
(1)二叉搜索樹的缺點
要手撕AVL樹，我們首先要知道什么是AVL樹。AVL樹是在二叉搜索樹的基礎(chǔ)之上改造的。當(dāng)我們插入的是一個有序的序列的時候，二叉搜素樹會使用一條直線來進行存儲，這樣并不利于查找。
當(dāng)遇到這種情況的時候我們就需要對這棵樹來進行調(diào)整。AVL樹會通過旋轉(zhuǎn)等操作，來規(guī)避這種情況。最終滿足每一個節(jié)點的平衡因子的絕對值<=1，從而達(dá)到近似平衡的目的。
節(jié)點的平衡因子值=右子樹的高度-左子樹高度
(2)定義節(jié)點
在AVL樹中，除了需要定義平衡因子bf之外，還需要定義指向節(jié)點父節(jié)點的指針。方便我們來進行平衡因子的更新。
struct AVLTreeNode
{
AVLTreeNode* right;
AVLTreeNode* left;
AVLTreeNode* parent;
pair<int, int> _kv;
int _bf;
AVLTreeNode(pair<int, int> kv)
:right(nullptr)
,left(nullptr)
,parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
同時和map一樣，我們使用pair類型來進行數(shù)據(jù)的存儲。
2.插入
(1)拆分
AVL樹的插入就是AVL樹的精髓所在，我們在插入節(jié)點的同時還需要對平衡因子進行控制。
AVL樹的插入我們可以拆分成五個函數(shù)，其中四個為旋轉(zhuǎn)函數(shù)，一個為主要的插入函數(shù)。
而這個主要的插入函數(shù)，我們還可以將其分為三個部分：找節(jié)點，插節(jié)點，更新平衡因子。而更新平衡因子后就需要判斷是否需要進行旋轉(zhuǎn)的操作。
在進行插入之前，我們將插入的節(jié)點定義為kv。
(2)找節(jié)點與插節(jié)點
這一過程與二叉搜索樹是相同的，這里就不多贅述了。二叉搜索樹
直接上代碼：
//初始化頭結(jié)點
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入節(jié)點的位置
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
{
assert(false);
}
}
//插入節(jié)點
cur = new Node(kv);
if (parent->_kv.first<kv.first)
{
parent->right = cur;
cur->parent = parent;
}
else if (parent->_kv.first>kv.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
assert(false);
}
(3)更新平衡因子與旋轉(zhuǎn)
更新平衡因子
每當(dāng)我們插入一個節(jié)點的時候，就需要對該節(jié)點的所有父輩節(jié)點來進行平衡因子的更新。注意，當(dāng)插入節(jié)點后，只有其父輩節(jié)點的平衡因子才會受到影響，而其他節(jié)點的平衡因子不會被影響。
可以根據(jù)每個節(jié)點的parent來找到其父親節(jié)點，從而逐漸向上更新平衡因子。
當(dāng)遇到以下兩種情況平衡因子的更新停止。
1.某一父輩節(jié)點的平衡因子為0。
2.更新到根節(jié)點。
旋轉(zhuǎn)
當(dāng)更新之后的平衡因子為2或者-2的時候，不符合AVL樹的平衡因子在-1~1之間的定義，此時需要發(fā)生旋轉(zhuǎn)。觸發(fā)旋轉(zhuǎn)的條件與當(dāng)前節(jié)點cur和它的parent有關(guān)。
當(dāng)parent和cur的平衡因子分別為：
(1)2和1，觸發(fā)左旋
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
用一張圖來表示一下這個過程：
h表示某樹的高度，當(dāng)在紅色部分處插入一個節(jié)點時，60的平衡因子變?yōu)?，30的平衡因子變?yōu)?。
此時就需要發(fā)生旋轉(zhuǎn)：
通過旋轉(zhuǎn)使樹重新變成一棵AVL樹，整個過程分為三步：
- 1.60的左子樹置為30,30的右子樹置為60的左子樹。
- 2.將30與更上層的父輩節(jié)點鏈接起來。
- 3.將30和60的平衡因子都更新為0。
注意，由于AVL樹是三叉樹，因此在鏈接的時候需要將父節(jié)點也鏈接起來。因此在將60的左子樹鏈接到30的右子樹的時候，需要進行判空來避免空指針的解引用：
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
(2)-2和-1，觸發(fā)右旋
右旋同樣分為三步：
- 1.將30的右鏈接到60的左子樹。將60鏈接到30的右。
- 2.將30與上層節(jié)點鏈接起來。
- 3.將30和60的平衡因子都更新為0。
void RotateR(Node* parent)
{
Node* cur = parent->left;
Node* curL = cur->left;
Node* curR = cur->right;
Node* parentParent = parent->parent;
parent->left = curR;
if (curR)
curR->parent = parent;
cur->right = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
cur->_bf = 0;
parent->_bf = 0;
}
(3)-2和1，左右雙旋
當(dāng)為-2和1或者2和-1的時候，僅僅靠單旋是解決不了問題的，這個時候我們就需要進行雙旋：
左單旋：
右單旋：
無論是在紅色部分或者藍(lán)色部分插入節(jié)點，都會導(dǎo)致發(fā)生左右雙旋。
左右雙旋分為三步：
- 1.對30節(jié)點進行左單旋。
- 2.對90節(jié)點進行右單旋。
- 3.根據(jù)60的平衡因子來更新30和90的平衡因子：當(dāng)60的平衡因子為0時，30和90的平衡因子也為0；當(dāng)60的平衡因子為1時，30的平衡因子為-1，90的平衡因子為0；當(dāng)60的平衡因子為-1時，30的平衡因子為0,90的平衡因子為1。
void RotateLR(Node* parent)
{
Node* subL = parent->left;
Node* subLR =subL->right;
int bf = subLR->_bf;
RotateL(parent->left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subLR->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
}
(4)2和-1，右左雙旋
右單旋：
左單旋：
無論是在紅色部分或者藍(lán)色部分插入節(jié)點，都會導(dǎo)致發(fā)生右左雙旋。
右左雙旋分為三步：
- 1.對90節(jié)點進行右單旋。
- 2.對30節(jié)點進行左單旋。
- 3.根據(jù)60的平衡因子來更新30和90的平衡因子：當(dāng)60的平衡因子為0時，30和90的平衡因子也為0；當(dāng)60的平衡因子為1時，30的平衡因子為-1，90的平衡因子為0；當(dāng)60的平衡因子為-1時，30的平衡因子為0,90的平衡因子為1。
void RotateRL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
int bf = subRL->_bf;
RotateR(parent->right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
3.判斷
我們可以建立一個函數(shù)來判斷一棵樹是否為AVL樹。
我們使用遞歸來進行這一過程，依次判斷各個子樹是否為AVL樹。
要判斷我們就需要知道每一棵樹的高度，此時我們需要構(gòu)造一個求樹的高度的函數(shù)Height。它也由遞歸來實現(xiàn)。
int Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
if ((rightHeight - leftHeight) != root->_bf)
{
cout << "現(xiàn)在是：" << root->_bf << endl;
cout << "應(yīng)該是：" << rightHeight - leftHeight << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
}
4.完整代碼及測試代碼
完整代碼
#pragma once
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct AVLTreeNode
{
AVLTreeNode* right;
AVLTreeNode* left;
AVLTreeNode* parent;
pair<int, int> _kv;
int _bf;
AVLTreeNode(pair<int, int> kv)
:right(nullptr)
,left(nullptr)
,parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
class AVLTree
{
typedef AVLTreeNode Node;
public:
AVLTree()
{
_root = nullptr;
}
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->right);
}
int Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->left);
int rightHeight = Height(root->right);
if ((rightHeight - leftHeight) != root->_bf)
{
cout << "現(xiàn)在是：" << root->_bf << endl;
cout << "應(yīng)該是：" << rightHeight - leftHeight << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
}
//右單旋
void RotateR(Node* parent)
{
Node* cur = parent->left;
Node* curL = cur->left;
Node* curR = cur->right;
Node* parentParent = parent->parent;
parent->left = curR;
if (curR)
curR->parent = parent;
cur->right = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
cur->_bf = 0;
parent->_bf = 0;
}
//左單旋
void RotateL(Node* parent)
{
Node* cur = parent->right;
Node* curL = cur->left;
Node* parentParent = parent->parent;
parent->right = curL;
if (curL)
curL->parent = parent;
cur->left = parent;
parent->parent = cur;
if (parent == _root)
{
_root = cur;
_root->parent = nullptr;
}
else
{
if (parentParent->left == parent)
{
parentParent->left = cur;
cur->parent = parentParent;
}
else if (parentParent->right == parent)
{
parentParent->right = cur;
cur->parent = parentParent;
}
else
{
assert(false);
}
}
parent->_bf = 0;
cur->_bf = 0;
}
//左右雙旋
void RotateLR(Node* parent)
{
Node* subL = parent->left;
Node* subLR =subL->right;
int bf = subLR->_bf;
RotateL(parent->left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subLR->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
}
//右左雙旋
void RotateRL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
int bf = subRL->_bf;
RotateR(parent->right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
bool InsertNode(pair<int, int> kv)
{
//初始化頭結(jié)點
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入節(jié)點的位置
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
{
assert(false);
}
}
//插入節(jié)點
cur = new Node(kv);
if (parent->_kv.first<kv.first)
{
parent->right = cur;
cur->parent = parent;
}
else if (parent->_kv.first>kv.first)
{
parent->left = cur;
cur->parent = parent;
}
else
{
assert(false);
}
//更新插入節(jié)點以上的平衡因子
while (parent)
{
if (cur == parent->left)
{
parent->_bf--;
}
else if (cur == parent->right)
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
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);
}
}
}
private:
Node* _root;
};
測試代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include"AVLTree.h"
void TestRotateR()
{
AVLTree t;
t.InsertNode(make_pair(5, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(0, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRotateL()
{
AVLTree t;
t.InsertNode(make_pair(0, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(5, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void Testbf()
{
AVLTree t;
t.InsertNode(make_pair(5, 1));
t.InsertNode(make_pair(7, 1));
t.InsertNode(make_pair(3, 1));
t.InsertNode(make_pair(4, 1));
t.InsertNode(make_pair(2, 1));
t.InsertNode(make_pair(8, 1));
t.InsertNode(make_pair(9, 1));
t.InsertNode(make_pair(6, 1));
t.InsertNode(make_pair(1, 1));
t.InsertNode(make_pair(11, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRL()
{
AVLTree t;
t.InsertNode(make_pair(60, 1));
t.InsertNode(make_pair(50, 1));
t.InsertNode(make_pair(90, 1));
t.InsertNode(make_pair(100, 1));
t.InsertNode(make_pair(80, 1));
t.InsertNode(make_pair(70, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestLR()
{
AVLTree t;
t.InsertNode(make_pair(90, 1));
t.InsertNode(make_pair(100, 1));
t.InsertNode(make_pair(60, 1));
t.InsertNode(make_pair(50, 1));
t.InsertNode(make_pair(70, 1));
t.InsertNode(make_pair(80, 1));
t.InOrder();
cout << t.IsBalance() << endl;
}
int main()
{
//TestRotateR();
//Testbf();
//TestRotateL();
//TestRL();
TestLR();
}
以上就是C++數(shù)據(jù)結(jié)構(gòu)之AVL樹的實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ AVL樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決
這篇文章主要介紹了c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要為大家詳細(xì)介紹了OpenGL實現(xiàn)鼠標(biāo)移動方塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
C語言這門課程在計算機的基礎(chǔ)教學(xué)中一直占有比較重要的地位，然而要想突破C語言的學(xué)習(xí)，對指針的掌握是非常重要的，本文將具體針對指針的基礎(chǔ)做詳盡的介紹2022-06-06
這篇文章主要為大家介紹了C++面試八股文之了解auto關(guān)鍵字問題解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
本篇文章是C語言編程篇，主要為大家介紹C語言編程中數(shù)據(jù)在內(nèi)存中存儲解析，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09
這篇文章主要為大家詳細(xì)介紹了Qt編寫秒表功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
QT實現(xiàn)按鈕開關(guān)Form窗體的效果的示例代碼
本文主要介紹了QT實現(xiàn)按鈕開關(guān)Form窗體的效果的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要介紹了VS2019中CMake項目的簡單使用方法,需要的朋友可以參考下2020-02-02
這篇文章主要介紹了如何區(qū)分c++中的聲明與定義，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08
C++數(shù)據(jù)結(jié)構(gòu)之堆詳解
本文詳細(xì)講解了C++數(shù)據(jù)結(jié)構(gòu)之堆，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-04-04