C++數(shù)據(jù)結(jié)構(gòu)之AVL樹的實(shí)現(xiàn)
更新時(shí)間：2022年06月09日 14:31:28 作者：賣寂寞的小男孩
AVL樹是高度平衡的而二叉樹,它的特點(diǎn)是AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1,本文主要給大家介紹了C++如何實(shí)現(xiàn)AVL樹,需要的朋友可以參考下
1.概念
(1)二叉搜索樹的缺點(diǎn)
要手撕AVL樹，我們首先要知道什么是AVL樹。AVL樹是在二叉搜索樹的基礎(chǔ)之上改造的。當(dāng)我們插入的是一個(gè)有序的序列的時(shí)候，二叉搜素樹會(huì)使用一條直線來進(jìn)行存儲(chǔ)，這樣并不利于查找。
當(dāng)遇到這種情況的時(shí)候我們就需要對(duì)這棵樹來進(jìn)行調(diào)整。AVL樹會(huì)通過旋轉(zhuǎn)等操作，來規(guī)避這種情況。最終滿足每一個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值<=1，從而達(dá)到近似平衡的目的。
節(jié)點(diǎn)的平衡因子值=右子樹的高度-左子樹高度
(2)定義節(jié)點(diǎn)
在AVL樹中，除了需要定義平衡因子bf之外，還需要定義指向節(jié)點(diǎn)父節(jié)點(diǎn)的指針。方便我們來進(jìn)行平衡因子的更新。
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)
{}
};
同時(shí)和map一樣，我們使用pair類型來進(jìn)行數(shù)據(jù)的存儲(chǔ)。
2.插入
(1)拆分
AVL樹的插入就是AVL樹的精髓所在，我們在插入節(jié)點(diǎn)的同時(shí)還需要對(duì)平衡因子進(jìn)行控制。
AVL樹的插入我們可以拆分成五個(gè)函數(shù)，其中四個(gè)為旋轉(zhuǎn)函數(shù)，一個(gè)為主要的插入函數(shù)。
而這個(gè)主要的插入函數(shù)，我們還可以將其分為三個(gè)部分：找節(jié)點(diǎn)，插節(jié)點(diǎn)，更新平衡因子。而更新平衡因子后就需要判斷是否需要進(jìn)行旋轉(zhuǎn)的操作。
在進(jìn)行插入之前，我們將插入的節(jié)點(diǎn)定義為kv。
(2)找節(jié)點(diǎn)與插節(jié)點(diǎn)
這一過程與二叉搜索樹是相同的，這里就不多贅述了。二叉搜索樹
直接上代碼：
//初始化頭結(jié)點(diǎn)
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入節(jié)點(diǎn)的位置
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é)點(diǎn)
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)我們插入一個(gè)節(jié)點(diǎn)的時(shí)候，就需要對(duì)該節(jié)點(diǎn)的所有父輩節(jié)點(diǎn)來進(jìn)行平衡因子的更新。注意，當(dāng)插入節(jié)點(diǎn)后，只有其父輩節(jié)點(diǎn)的平衡因子才會(huì)受到影響，而其他節(jié)點(diǎn)的平衡因子不會(huì)被影響。
可以根據(jù)每個(gè)節(jié)點(diǎn)的parent來找到其父親節(jié)點(diǎn)，從而逐漸向上更新平衡因子。
當(dāng)遇到以下兩種情況平衡因子的更新停止。
1.某一父輩節(jié)點(diǎn)的平衡因子為0。
2.更新到根節(jié)點(diǎn)。
旋轉(zhuǎn)
當(dāng)更新之后的平衡因子為2或者-2的時(shí)候，不符合AVL樹的平衡因子在-1~1之間的定義，此時(shí)需要發(fā)生旋轉(zhuǎn)。觸發(fā)旋轉(zhuǎn)的條件與當(dāng)前節(jié)點(diǎn)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;
}
用一張圖來表示一下這個(gè)過程：
h表示某樹的高度，當(dāng)在紅色部分處插入一個(gè)節(jié)點(diǎn)時(shí)，60的平衡因子變?yōu)?，30的平衡因子變?yōu)?。
此時(shí)就需要發(fā)生旋轉(zhuǎn)：
通過旋轉(zhuǎn)使樹重新變成一棵AVL樹，整個(gè)過程分為三步：
- 1.60的左子樹置為30,30的右子樹置為60的左子樹。
- 2.將30與更上層的父輩節(jié)點(diǎn)鏈接起來。
- 3.將30和60的平衡因子都更新為0。
注意，由于AVL樹是三叉樹，因此在鏈接的時(shí)候需要將父節(jié)點(diǎn)也鏈接起來。因此在將60的左子樹鏈接到30的右子樹的時(shí)候，需要進(jìn)行判空來避免空指針的解引用：
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é)點(diǎn)鏈接起來。
- 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的時(shí)候，僅僅靠單旋是解決不了問題的，這個(gè)時(shí)候我們就需要進(jìn)行雙旋：
左單旋：
右單旋：
無論是在紅色部分或者藍(lán)色部分插入節(jié)點(diǎn)，都會(huì)導(dǎo)致發(fā)生左右雙旋。
左右雙旋分為三步：
- 1.對(duì)30節(jié)點(diǎn)進(jìn)行左單旋。
- 2.對(duì)90節(jié)點(diǎn)進(jìn)行右單旋。
- 3.根據(jù)60的平衡因子來更新30和90的平衡因子：當(dāng)60的平衡因子為0時(shí)，30和90的平衡因子也為0；當(dāng)60的平衡因子為1時(shí)，30的平衡因子為-1，90的平衡因子為0；當(dāng)60的平衡因子為-1時(shí)，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é)點(diǎn)，都會(huì)導(dǎo)致發(fā)生右左雙旋。
右左雙旋分為三步：
- 1.對(duì)90節(jié)點(diǎn)進(jìn)行右單旋。
- 2.對(duì)30節(jié)點(diǎn)進(jìn)行左單旋。
- 3.根據(jù)60的平衡因子來更新30和90的平衡因子：當(dāng)60的平衡因子為0時(shí)，30和90的平衡因子也為0；當(dāng)60的平衡因子為1時(shí)，30的平衡因子為-1，90的平衡因子為0；當(dāng)60的平衡因子為-1時(shí)，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.判斷
我們可以建立一個(gè)函數(shù)來判斷一棵樹是否為AVL樹。
我們使用遞歸來進(jìn)行這一過程，依次判斷各個(gè)子樹是否為AVL樹。
要判斷我們就需要知道每一棵樹的高度，此時(shí)我們需要構(gòu)造一個(gè)求樹的高度的函數(shù)Height。它也由遞歸來實(shí)現(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é)點(diǎn)
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
//找到要插入節(jié)點(diǎn)的位置
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é)點(diǎn)
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é)點(diǎn)以上的平衡因子
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樹的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ AVL樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
仿現(xiàn)代C++智能指針實(shí)現(xiàn)引用計(jì)數(shù)
這篇文章主要為大家詳細(xì)介紹了如何仿現(xiàn)代C++智能指針實(shí)現(xiàn)引用計(jì)數(shù),文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以了解下2024-03-03
這篇文章主要為大家詳細(xì)介紹了C++ Coroutine的簡單學(xué)習(xí)教程，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08
三子棋(井字棋)我們的童年或多或少都體驗(yàn)過這個(gè)游戲的樂趣,本子隨手一畫就是一局游戲的開始,下面這篇文章主要給大家介紹了關(guān)于200行C語言代碼實(shí)現(xiàn)簡易三子棋游戲的相關(guān)資料,需要的朋友可以參考下2023-05-05
使用?Visual?Studio?2022?開發(fā)?Linux?C++?應(yīng)用程序的過程詳解
Visual?Studio?2022?引入了用于?Linux?C++?開發(fā)的本機(jī)?WSL2?工具集，可以構(gòu)建和調(diào)試?Linux?C++?代碼，并提供了非常好的?Linux?文件系統(tǒng)性能、GUI?支持和完整的系統(tǒng)調(diào)用兼容性，這篇文章主要介紹了使用Visual?Studio?2022?開發(fā)?Linux?C++?應(yīng)用程序,需要的朋友可以參考下2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言俄羅斯方塊游戲課程設(shè)計(jì)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
C語言標(biāo)準(zhǔn)庫＜math.h＞和＜setjmp.h＞的實(shí)現(xiàn)
本文主要介紹了C語言標(biāo)準(zhǔn)庫＜math.h＞和＜setjmp.h＞的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-11-11
C++實(shí)現(xiàn)LeetCode(202.快樂數(shù))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(202.快樂數(shù)),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)flappy bird小游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要介紹了C++抽獎(jiǎng)程序?qū)崿F(xiàn)方法,實(shí)例分析了C++隨機(jī)數(shù)的生成技巧與抽獎(jiǎng)程序的實(shí)現(xiàn)方法,需要的朋友可以參考下2015-07-07
C++11規(guī)定，允許將變量聲明為constexpr類型以便由編譯器來驗(yàn)證變量的值是否是一個(gè)常量表達(dá)式，這篇文章主要介紹了C++11/C++14中constexpr的使用,需要的朋友可以參考下2023-06-06