<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
C++資料結構之AVL樹的實現
2022-06-09 18:01:20
1.概念
(1)二元搜尋樹的缺點
要手撕AVL樹，我們首先要知道什麼是AVL樹。AVL樹是在二元搜尋樹的基礎之上改造的。當我們插入的是一個有序的序列的時候，二叉搜素樹會使用一條直線來進行儲存，這樣並不利於查詢。
當遇到這種情況的時候我們就需要對這棵樹來進行調整。AVL樹會通過旋轉等操作，來規避這種情況。最終滿足每一個節點的平衡因子的絕對值<=1，從而達到近似平衡的目的。
節點的平衡因子值=右子樹的高度-左子樹高度
(2)定義節點
在AVL樹中，除了需要定義平衡因子bf之外，還需要定義指向節點父節點的指標。方便我們來進行平衡因子的更新。
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型別來進行資料的儲存。
2.插入
(1)拆分
AVL樹的插入就是AVL樹的精髓所在，我們在插入節點的同時還需要對平衡因子進行控制。
AVL樹的插入我們可以拆分成五個函數，其中四個為旋轉函數，一個為主要的插入函數。
而這個主要的插入函數，我們還可以將其分為三個部分：找節點，插節點，更新平衡因子。而更新平衡因子後就需要判斷是否需要進行旋轉的操作。
在進行插入之前，我們將插入的節點定義為kv。
(2)找節點與插節點
這一過程與二元搜尋樹是相同的，這裡就不多贅述了。二元搜尋樹
直接上程式碼：
//初始化頭結點
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
{
assert(false);
}
}
//插入節點
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)更新平衡因子與旋轉
更新平衡因子
每當我們插入一個節點的時候，就需要對該節點的所有父輩節點來進行平衡因子的更新。注意，當插入節點後，只有其父輩節點的平衡因子才會受到影響，而其他節點的平衡因子不會被影響。
可以根據每個節點的parent來找到其父親節點，從而逐漸向上更新平衡因子。
當遇到以下兩種情況平衡因子的更新停止。
1.某一父輩節點的平衡因子為0。
2.更新到根節點。
旋轉
當更新之後的平衡因子為2或者-2的時候，不符合AVL樹的平衡因子在-1~1之間的定義，此時需要發生旋轉。觸發旋轉的條件與當前節點cur和它的parent有關。
當parent和cur的平衡因子分別為：
(1)2和1，觸發左旋
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表示某樹的高度，當在紅色部分處插入一個節點時，60的平衡因子變為1，30的平衡因子變為2。
此時就需要發生旋轉：
通過旋轉使樹重新變成一棵AVL樹，整個過程分為三步：
- 1.60的左子樹置為30,30的右子樹置為60的左子樹。
- 2.將30與更上層的父輩節點連結起來。
- 3.將30和60的平衡因子都更新為0。
注意，由於AVL樹是三元樹，因此在連結的時候需要將父節點也連結起來。因此在將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，觸發右旋
右旋同樣分為三步：
- 1.將30的右連結到60的左子樹。將60連結到30的右。
- 2.將30與上層節點連結起來。
- 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，左右雙旋
當為-2和1或者2和-1的時候，僅僅靠單旋是解決不了問題的，這個時候我們就需要進行雙旋：
左單旋：
右單旋：
無論是在紅色部分或者藍色部分插入節點，都會導致發生左右雙旋。
左右雙旋分為三步：
- 1.對30節點進行左單旋。
- 2.對90節點進行右單旋。
- 3.根據60的平衡因子來更新30和90的平衡因子：當60的平衡因子為0時，30和90的平衡因子也為0；當60的平衡因子為1時，30的平衡因子為-1，90的平衡因子為0；當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，右左雙旋
右單旋：
左單旋：
無論是在紅色部分或者藍色部分插入節點，都會導致發生右左雙旋。
右左雙旋分為三步：
- 1.對90節點進行右單旋。
- 2.對30節點進行左單旋。
- 3.根據60的平衡因子來更新30和90的平衡因子：當60的平衡因子為0時，30和90的平衡因子也為0；當60的平衡因子為1時，30的平衡因子為-1，90的平衡因子為0；當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.判斷
我們可以建立一個函數來判斷一棵樹是否為AVL樹。
我們使用遞回來進行這一過程，依次判斷各個子樹是否為AVL樹。
要判斷我們就需要知道每一棵樹的高度，此時我們需要構造一個求樹的高度的函數Height。它也由遞回來實現。
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 << "現在是：" << root->_bf << endl;
cout << "應該是：" << 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 << "現在是：" << root->_bf << endl;
cout << "應該是：" << 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)
{
//初始化頭結點
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
{
assert(false);
}
}
//插入節點
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);
}
//更新插入節點以上的平衡因子
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++資料結構之AVL樹的實現的詳細內容，更多關於C++ AVL樹的資料請關注it145.com其它相關文章！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45