平衡二叉搜索樹(shù)-創(chuàng)新互聯(lián)
AVL樹(shù)又稱(chēng)高度平衡的二叉搜索樹(shù)，是1962年俄羅斯的數(shù)學(xué)家提出來(lái)的。它能保持二叉樹(shù)的高度平衡，盡量降低二叉樹(shù)的高度，減少樹(shù)的平均搜索長(zhǎng)度。
創(chuàng)新互聯(lián)長(zhǎng)期為上千家客戶(hù)提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為瑞安企業(yè)提供專(zhuān)業(yè)的成都做網(wǎng)站、成都網(wǎng)站建設(shè)，瑞安網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。AVL的性質(zhì)：
（1）左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。
（2）樹(shù)中的每個(gè)左子樹(shù)和右子樹(shù)都是AVL樹(shù)。
（3）每個(gè)節(jié)點(diǎn)都有一個(gè)平衡因子，任一節(jié)點(diǎn)的平衡因子是-1，0，1（每個(gè)節(jié)點(diǎn)的平衡因子等于右子樹(shù)的高度減去左子樹(shù)的高度）。
代碼實(shí)現(xiàn)如下：
#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)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _bf(0)
{}
};
template<class K,class V>
class AVLTree{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(NULL)
{}
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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key,value);
if (parent->_key > key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//更新平衡因子
//不平衡，則進(jìn)行旋轉(zhuǎn)
while (parent)
{
if (parent->_right==cur)
parent->_bf++;
else
parent->_bf--;
//父節(jié)點(diǎn)平衡因子為0時(shí)，退出（說(shuō)明父節(jié)點(diǎn)的兩邊高度一樣，算路徑長(zhǎng)度的話(huà)都一樣，沒(méi)有影響）
if (parent->_bf == 0)
break;
//父節(jié)點(diǎn)平衡因子為1或-1的時(shí)候（說(shuō)明是從0+1或0-1得來(lái)的），父節(jié)點(diǎn)兩邊高度不同，故需要繼續(xù)更新平衡因子
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
//父節(jié)點(diǎn)平衡因子為2或-2時(shí)，旋轉(zhuǎn)
else //(parent->_bf==2||parent->_bf==-2) 旋轉(zhuǎn)
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)//右單旋
{
_RotateR(parent);
}
else //(cur->_bf==1) 左右單旋
{
_RotateLR(parent);
}
}
else //(parent->_bf==2)
{
if (cur->_bf == 1) //左單旋
{
_RotateL(parent);
}
else //(cur->_bf==-1)右左單旋
{
_RotateRL(parent);
}
}
break;
}
}
}
Node* Find(const K& key)
{
if (_root == NULL)
return false;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return cur;
}
return false;
}
bool Remove(const K& key)
{
if (_root == NULL)
return false;
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
Node* del;
if (cur->_right == NULL)
{
del = cur;
if (parent == NULL)
{
_root = cur->_left;
//_root->_bf = 0;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
parent->_bf++;
}
else
{
parent->_right = cur->_left;
parent->_bf--;
}
}
delete del;
}
else if (cur->_left == NULL)
{
del = cur;
if (parent == NULL)
{
_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 del;
}
else
{
parent = cur;
Node* left = cur->_right;
while (left->_left)
{
parent = left;
left = left->_left;
}
del = left;
cur->_key = left->_key;
cur->_value = left->_value;
if (parent->_left == left)
{
parent->_left = left->_right;
parent->_bf++;
}
else
{
parent->_right = left->_right;
parent->_bf--;
}
delete del;
}
break;
}
}
if (cur == NULL)
{
return false;
}
while (parent)
{
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
break;
}
else //parent->_bf=2||parent->_bf=-2
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)
_RotateR(parent);
else //cur->_bf=1
_RotateLR(parent);
}
else
{
if (cur->_bf == 1)
_RotateL(parent);
else
_RotateRL(parent);
}
break;
}
}
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//判斷這棵樹(shù)是否是平衡搜索樹(shù)
bool IsBlance()
{
return _IsBlance(_root);
}
protected:
void _RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR=subL->_right;
parent->_left = subLR;
if (subLR != NULL)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (ppNode == NULL)
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
subL->_parent = ppNode;
}
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 != NULL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (ppNode == NULL)
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
subR->_parent = ppNode;
}
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) //從subRL的右邊插入
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1) //從subRL的左邊插入
{
parent->_bf = 0;
subR->_bf = 1;
}
else //(bf=0)
{
parent->_bf = 0;
subR->_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 = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else //bf=0
{
parent->_bf = 0;
subL->_bf = 0;
}
subLR->_bf = 0;
}
bool _IsBlance(Node* root)
{
if (root == NULL)
return true;
int right = _Height(root->_right);
int left = _Height(root->_left);
if (right - left != root->_bf || abs(right - left) >= 2)
{
cout << "平衡因子異常" << root->_key << endl;
}
return _IsBlance(root->_left) && _IsBlance(root->_right);
}
int _Height(Node* root)
{
if (root == NULL)
return 0;
int right = _Height(root->_right);
int left = _Height(root->_left);
if (right > left)
return (right + 1);
else
return (left + 1);
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
else
{
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
}
protected:
Node* _root;
};
#include "AVLTree.h"
void Test1()
{
int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> avl;
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
avl.Insert(a[i],i);
}
avl.InOrder();
cout<<avl.IsBlance()<<endl;
AVLTreeNode<int, int>* ret1 = avl.Find(18);
if (ret1)
cout << ret1->_key << ":" << ret1->_value << endl;
else
cout << "不存在ret1" << endl;
AVLTreeNode<int, int>* ret2 = avl.Find(1);
if (ret2)
cout << ret2->_key << ":" << ret2->_value << endl;
else
cout << "不存在ret2" << endl;
avl.Remove(26);
avl.Remove(18);
avl.Remove(15);
avl.InOrder();
avl.Remove(3);
cout << avl.Remove(7) << endl;
avl.Remove(7);
avl.Remove(9);
avl.Remove(11);
avl.Remove(14);
avl.Remove(15);
cout << avl.Remove(100) << endl;
avl.Remove(16);
avl.Remove(18);
avl.Remove(26);
avl.InOrder();
}
void Test2()
{
int a[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> avl;
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
avl.Insert(a[i], i);
}
avl.InOrder();
cout << avl.IsBlance() << endl;
AVLTreeNode<int, int>* ret1 = avl.Find(5);
if (ret1)
cout << ret1->_key << ":" << ret1->_value << endl;
else
cout << "不存在ret1" << endl;
AVLTreeNode<int, int>* ret2 = avl.Find(88);
if (ret2)
cout << ret2->_key << ":" << ret2->_value << endl;
else
cout << "不存在ret2" << endl;
avl.Remove(14);
avl.Remove(16);
avl.Remove(7);
avl.InOrder();
avl.Remove(15);
avl.Remove(6);
avl.Remove(5);
cout << avl.Remove(4) << endl;
avl.Remove(4);
avl.Remove(3);
avl.Remove(2);
avl.Remove(1);
cout << avl.Remove(100) << endl;
avl.Remove(7);
avl.Remove(16);
avl.InOrder();
}
int main()
{
Test1();
cout << endl;
cout << endl;
Test2();
return 0;
}實(shí)現(xiàn)結(jié)果：
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。
文章名稱(chēng)：平衡二叉搜索樹(shù)-創(chuàng)新互聯(lián)
本文路徑：http://bm7419.com/article14/cedide.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、小程序開(kāi)發(fā)、域名注冊(cè)、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站策劃、App設(shè)計(jì)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
- Linux之恢復(fù)誤刪除文件-創(chuàng)新互聯(lián)
- 進(jìn)修什么單片機(jī)-創(chuàng)新互聯(lián)
- CSS屬性text-overflow的示例分析-創(chuàng)新互聯(lián)
- 【ocx疑難雜癥0】淺談OCX開(kāi)發(fā)注冊(cè)“逐用戶(hù)重定向”問(wèn)題-創(chuàng)新互聯(lián)
- pandas將list切分后存入DataFrame中的實(shí)例-創(chuàng)新互聯(lián)
- SAP試圖取消審批報(bào)錯(cuò)怎么解決-創(chuàng)新互聯(lián)
- bootstrap框架有哪些組件-創(chuàng)新互聯(lián)
- 響應(yīng)式網(wǎng)站建設(shè)要注意哪些細(xì)節(jié) 2022-05-05
- 【網(wǎng)站建設(shè)】分析響應(yīng)式網(wǎng)站制作和營(yíng)銷(xiāo)型網(wǎng)站制作各自的特征和用途 2021-10-25
- 網(wǎng)絡(luò)營(yíng)銷(xiāo)如何從響應(yīng)式網(wǎng)站設(shè)計(jì)中獲益 2023-02-13
- 自適應(yīng)本質(zhì)上不同于響應(yīng)式網(wǎng)站建設(shè)時(shí)應(yīng)慎重選型 2022-05-23
- 響應(yīng)式網(wǎng)站建設(shè)價(jià)格怎么高出這么多 2016-10-29
- 響應(yīng)式網(wǎng)站設(shè)計(jì)中的長(zhǎng)寬比問(wèn)題淺析 2016-12-16
- 響應(yīng)式網(wǎng)站建設(shè)有哪些要注意的標(biāo)準(zhǔn)？ 2022-10-31
- 響應(yīng)式網(wǎng)站設(shè)計(jì)如何使SEO受益 2019-04-02
- 響應(yīng)式網(wǎng)站制作應(yīng)該主注意哪些問(wèn)題 2016-10-02
- 淺談響應(yīng)式網(wǎng)站設(shè)計(jì)是全能的嗎 2022-06-24
- 響應(yīng)式網(wǎng)站建設(shè)常見(jiàn)的問(wèn)題有哪些？ 2022-05-23
- 響應(yīng)式網(wǎng)站制作優(yōu)勢(shì)有哪些？ 2013-10-22