AVL樹增刪查找
AVL樹：又稱高度平衡的二叉搜索樹，它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長度。
專業(yè)成都網(wǎng)站建設(shè)公司，做排名好的好網(wǎng)站，排在同行前面，為您帶來客戶和效益!成都創(chuàng)新互聯(lián)公司為您提供成都網(wǎng)站建設(shè)，五站合一網(wǎng)站設(shè)計制作，服務(wù)好的網(wǎng)站設(shè)計公司，成都網(wǎng)站制作、做網(wǎng)站負(fù)責(zé)任的成都網(wǎng)站制作公司!
AVL樹的性質(zhì)
左子樹和右子樹的高度之差的絕對值不超過1
樹中的每個左子樹和右子樹都是AVL樹
#pragma once
#include<iostream>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
K _key;
V _value;
int _bf;
AVLTreeNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, _bf(0)
{}
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(NULL)
{}
~AVLTree()
{}
bool Insert(const K& key, const V& value)
{
if (_root == NULL)
{
_root = new Node(key, value);
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
{
cout << "該節(jié)點已經(jīng)存在" << endl;
return false;
}
}
cur = new Node(key, value);
if (parent->_key < key)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//更新平衡因子
while (parent)
{
if (cur == parent->_right)
++parent->_bf;
else if (cur == parent->_left)
--parent->_bf;
if (parent->_bf == 0)
break;
else if (parent->_bf == -1 || parent->_bf == 1)
{
cur = parent;
parent = cur->_parent;
}
else //平衡因子為2或-2時的情況
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)
{ //左旋轉(zhuǎn)
RotateL(parent);
}
else if (cur->_bf==-1)
{
RotateRL(parent);
}
}
else
{
if (cur->_bf == -1)
{//右旋轉(zhuǎn)
RotateR(parent);
}
else if (cur->_bf == 1)
{
RotateLR(parent);
}
}
break;
}
}
return true;
}
Node* Find(const K& key)
{
if (_root == NULL)
return NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key>key)
{
cur = cur->_left;
}
else
{
cout << "找到該數(shù)" << endl;
return cur;
}
}
return NULL;
}
bool Remove(const K& key)
{
if (_root == NULL)
return false;
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
{
if (cur->_left == NULL && cur->_right == NULL)
{//1.左右都為空
if (parent == NULL)
_root = NULL;//若只有一個節(jié)點
else
{
if (parent->_left == cur)
parent->_bf++;
else
parent->_bf--;
}
delete cur;
cur = NULL;
}
else if (cur->_left&&cur->_right)
{//2.左右都不為空
Node* RightMin = cur->_right;
while (RightMin->_left)
{
parent = RightMin;
RightMin = RightMin->_left;
}
cur->_key = RightMin->_key;//采用替換法刪除
cur->_value = RightMin->_value;
if (parent->_left == RightMin)
{
parent->_bf++;
parent->_left = RightMin->_right;
}
else
{
parent->_bf--;
parent->_right = RightMin->_right;
}
delete RightMin;
RightMin = NULL;
}
else
{//3.左為空或右為空
if (cur->_left)
{//1).右為空
if (parent == NULL)
{//只有兩個節(jié)點，且為左孩子
_root = cur->_left;
_root->_bf = 0;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
parent->_bf++;
}
else
{
parent->_right = cur->_left;
parent->_bf--;
}
}
}
else
{//2).cur的左為空
if (parent == NULL)
{//只有兩個節(jié)點，且為左孩子
_root = cur->_right;
_root->_bf = 0;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
parent->_bf++;
}
else
{
parent->_right = cur->_right;
parent->_bf--;
}
}
}
delete cur;
cur = NULL;
}
break;
}
}
while (parent)
{//平衡因子為0或1、-1對這個樹的高度不會產(chǎn)生影響
if (parent->_parent->_left == parent)
parent->_parent->_bf++;
else
parent->_parent->_bf--;
if (parent->_parent->_bf == 0)
return true;
else if (parent->_parent->_bf==1 || parent->_parent->_bf==-1)
{
cur = parent;
parent = cur->_parent;
}
else
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent);
}
else
{
RotateLR(parent);
}
}
else
{
if (cur->_bf == 1)
{
RotateL(parent);
}
else
{
RotateRL(parent);
}
}
cout << "刪除成功" << endl;
return true;
}
}
return false;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppNode == NULL)//若要調(diào)整的節(jié)點為根節(jié)點
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left=subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
subL->_bf = parent->_bf= 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;//*若有父節(jié)點一定要指向它的父節(jié)點
if (ppNode== NULL)//若要調(diào)整的節(jié)點為根節(jié)點
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
subR->_bf =parent->_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 == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else //bf=0;
{
subR->_bf = parent->_bf = 0;
}
//subRL->_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 == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else //bf=0;
{
subL->_bf = parent->_bf = 0;
}
//subLR->_bf = 0;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
return _IsBalance(_root);
}
int Height()
{
return _Height(_root);
}
protected:
int _Height(Node* root)
{
if (root == NULL)
{
return 0;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
bool _IsBalance(Node* root)
{
if (root == NULL)
{
return true;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
if ((right-left) != root->_bf)
{
cout << root->_key <<"平衡因子異常" << endl;
return false;
}
return abs(right - left) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
protected:
Node* _root;
};
void Test()
{
AVLTree<int, int> avl;
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i <size; ++i)
{
avl.Insert(arr[i], i);
avl.IsBalance();
}
avl.InOrder();
avl.Remove(4);
avl.InOrder();
avl.IsBalance();
//avl.Remove(7);
//avl.InOrder();
//avl.IsBalance();
//avl.Remove(16);
//avl.InOrder();
//avl.IsBalance();
}
網(wǎng)站欄目：AVL樹增刪查找
當(dāng)前路徑：http://www.muchs.cn/article30/gdgdso.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計、面包屑導(dǎo)航、品牌網(wǎng)站制作、網(wǎng)站營銷、網(wǎng)站制作、企業(yè)網(wǎng)站制作
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 移動網(wǎng)站建設(shè)時這些問題千萬不能出現(xiàn)！ 2021-04-28
- 移動網(wǎng)站建設(shè)需要注意的問題 2022-12-17
- 如何從用戶角度進(jìn)行移動網(wǎng)站建設(shè)？ 2023-02-14
- 企業(yè)移動網(wǎng)站建設(shè)關(guān)鍵詞選取策略原則 2015-07-07
- 移動網(wǎng)站建設(shè)相關(guān)問題 2021-05-23
- 移動網(wǎng)站建設(shè)和微官網(wǎng)建設(shè)有哪些區(qū)別 2022-05-22
- 移動網(wǎng)站建設(shè)常見問題集錦 2016-11-08
- 關(guān)于企業(yè)移動網(wǎng)站建設(shè)推廣計劃一點建議 2021-07-29
- 移動網(wǎng)站建設(shè)用戶體驗介紹 2021-08-24
- 煙臺移動網(wǎng)站建設(shè)：做手機(jī)網(wǎng)站如何保證一個較快的加載速度？ 2021-11-11
- 一線品牌企業(yè)全站高端網(wǎng)站設(shè)計哪家好? 2022-06-14
- 移動網(wǎng)站建設(shè)時應(yīng)該注意的八大事項 2016-09-14