溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“C++數據結構之AVL樹如何實現”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++數據結構之AVL樹如何實現”吧！
要手撕AVL樹，我們首先要知道什么是AVL樹。AVL樹是在二叉搜索樹的基礎之上改造的。當我們插入的是一個有序的序列的時候，二叉搜素樹會使用一條直線來進行存儲，這樣并不利于查找。
當遇到這種情況的時候我們就需要對這棵樹來進行調整。AVL樹會通過旋轉等操作，來規避這種情況。最終滿足每一個節點的平衡因子的絕對值<=1，從而達到近似平衡的目的。
節點的平衡因子值=右子樹的高度-左子樹高度
在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類型來進行數據的存儲。
AVL樹的插入就是AVL樹的精髓所在，我們在插入節點的同時還需要對平衡因子進行控制。
AVL樹的插入我們可以拆分成五個函數，其中四個為旋轉函數，一個為主要的插入函數。
而這個主要的插入函數，我們還可以將其分為三個部分：找節點，插節點，更新平衡因子。而更新平衡因子后就需要判斷是否需要進行旋轉的操作。
在進行插入之前，我們將插入的節點定義為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);
}更新平衡因子
每當我們插入一個節點的時候，就需要對該節點的所有父輩節點來進行平衡因子的更新。注意，當插入節點后，只有其父輩節點的平衡因子才會受到影響，而其他節點的平衡因子不會被影響。
可以根據每個節點的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);
}
}我們可以建立一個函數來判斷一棵樹是否為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);
}#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樹如何實現這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
