高度平衡的二叉搜索樹—AVLTree
創(chuàng)新互聯(lián)建站-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比增城網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式增城網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋增城地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。
AVL樹
AVL樹又稱為高度平衡的二叉搜索樹，是1962年有俄羅斯的數(shù)學(xué)家G.M.Adel'son-Vel'skii和E.M.Landis提出來的。它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長度。
AVL樹的性質(zhì)
左子樹和右子樹的高度之差的絕對值不超過1
樹中的每個(gè)左子樹和右子樹都是AVL樹
每個(gè)節(jié)點(diǎn)都有一個(gè)平衡因子(balance factor--bf),任一節(jié)點(diǎn)的平衡因子是-1,0,1。(每個(gè)節(jié)點(diǎn)的平衡因子等于右子樹的高度減去左子樹的高度 )
AVL樹的效率
一棵AVL樹有N個(gè)節(jié)點(diǎn)，其高度可以保持在log2N，插入/刪除/查找的時(shí)間復(fù)雜度也是log2N。
（ps：log2N是表示log以2為底N的對數(shù)，evernote不支持公式。^^）
這里要注意在插入和刪除時(shí)對平衡因子BF的修改
插入
#pragma once
#include<iostream>
using namespace std;
#include<cmath>
template< class K, class V>
struct AVLBSTreeNode
{
AVLBSTreeNode<K, V>* _left;
AVLBSTreeNode<K, V>* _right;
AVLBSTreeNode<K, V>* _parent;
K _key;
V _value;
int _bf;//平衡因子
AVLBSTreeNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
, _parent(NULL)
, _key(key)
, _value(value)
, _bf(0)
{}
};
template<class K,class V>
class AVLBSTree
{
typedef AVLBSTreeNode<K, V> Node;
public:
AVLBSTree()
:_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 (cur == parent->_right)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
if (parent->_bf == 0)//平衡因子為0對這個(gè)樹的高度不會(huì)產(chǎn)生影響
{
break;
}
else if (parent->_bf == 1 || 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);//先右旋再左旋
}
}
break;
}
}
return true;
}
void Inorder()//中序遍歷
{
_Inorder(_root);
cout << endl;
}
bool IsBalance()//檢查平衡因子
{
return _IsBalance(_root);
}
Node* Find(const K& key)//查找
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == NULL && cur->_right == NULL)
{
if (parent == NULL)
{
_root = NULL;
}
else
{
if (parent->_left == cur)
{
parent->_left = NULL;
parent->_bf++;
}
else
{
parent->_right = NULL;
parent->_bf--;
}
}
delete cur;
}
else if (cur->_left == NULL && cur->_right != NULL)
{
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 cur;
}
else if (cur->_right == NULL && cur->_left != NULL)
{
if (parent == NULL)
{
_root = cur->_left;
_root++;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
parent->_bf++;
}
else
{
parent->_right = cur->_left;
parent->_bf--;
}
}
delete cur;
}
else
{
Node* parent = cur;
Node* left = cur->_right;
while (left->_left)
{
parent = left;
left = left->_left;
}
cur->_key = left->_key;
cur->_value = left->_value;
if (parent->_left == left)
{
parent->_bf++;
parent->_left = left->_right;
}
else
{
parent->_bf--;
parent->_right = left->_right;
}
delete left;
}
break;
}
}
while (parent)
{
if (parent->_bf == 0)//平衡因子為0對這個(gè)樹的高度不會(huì)產(chǎn)生影響
{
return true;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
return true;
}
else
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent);
}
else
{
RotateLR(parent);
}
}
else
{
if (cur->_bf == 1)
{
RotateL(parent);
}
else
{
RotateRL(parent);
}
}
break;
}
}
}
protected:
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)
{
_root = subL;
}
else
{
if (ppnode->_left == parent)
{
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;
if (ppnode == NULL)
{
_root = subR;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
}
subR->_parent = ppnode;
subR->_bf = parent->_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)//subLRde左邊插入
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)//subLR的右邊插入
{
parent->_bf = 0;
subL->_bf = -1;
}
else//subRL就是插入的元素
{
subL->_bf = parent->_bf = 0;
}
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 == -1)//subLRde左邊插入
{
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)//subLR的右邊插入
{
parent->_bf = -1;
subR->_bf = 0;
}
else//subRL就是插入的元素
{
subR->_bf = parent->_bf = 0;
}
subRL->_bf = 0;
}
void _Inorder(Node* root)
{
if (root == NULL)
{
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
bool _IsBalance(Node* root)
{
if (root == NULL)
{
return true;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
if ((right - left) != root->_bf || abs(right - left) >= 2)
{
cout << "not balance" << root->_key << endl;
return false;
}
return _IsBalance(root->_left) && _IsBalance(root->_right);
}
int _Height(Node* root)
{
if (root == NULL)
{
return 0;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
if (left > right)
{
return left + 1;
}
else
{
return right + 1;
}
}
protected:
Node* _root;
};
void Test()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16 ,14};
//int a[] = { 30, 35, 10, 20, 9, 18 };
//int a[] = { 10, 9, 30, 20, 40, 22 };
AVLBSTree<int, int> t;
int i = 0;
for (i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
t.Insert(a[i], i);
}
t.Remove(15);
t.Inorder();
cout<<"isblance"<<t.IsBalance()<<endl;
//cout << t.Find(50) << endl;
}
新聞名稱：高度平衡的二叉搜索樹—AVLTree
文章分享：http://aaarwkj.com/article0/igpooo.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站排名、動(dòng)態(tài)網(wǎng)站、網(wǎng)站收錄、網(wǎng)站營銷、網(wǎng)站設(shè)計(jì)公司
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
- 了解關(guān)鍵詞優(yōu)化的三個(gè)階段 2013-07-31
- 關(guān)鍵詞優(yōu)化使SEO效果更加明顯 2023-05-03
- 網(wǎng)站關(guān)鍵詞優(yōu)化的技巧有哪些? 2014-11-10
- 關(guān)鍵詞優(yōu)化作弊?這4點(diǎn)你不能不知道！ 2016-03-16
- 【SEO優(yōu)化】關(guān)于網(wǎng)站優(yōu)化內(nèi)容、關(guān)鍵詞優(yōu)化、網(wǎng)站結(jié)構(gòu)調(diào)整細(xì)節(jié) 2022-05-02
- SEO優(yōu)化該怎么做?關(guān)鍵詞優(yōu)化有好處嗎? 2014-05-08
- 關(guān)鍵詞優(yōu)化方法有哪些 2014-06-12
- 如何做好長尾關(guān)鍵詞優(yōu)化排名? 2013-09-07
- 成都關(guān)鍵詞優(yōu)化：百度顯示“網(wǎng)站標(biāo)題錯(cuò)誤”？？出現(xiàn)原因分析！ 2014-04-10
- seo關(guān)鍵詞優(yōu)化：網(wǎng)站快照查詢歷史因子方式 2020-11-27
- 網(wǎng)站關(guān)鍵詞優(yōu)化應(yīng)該怎么做才能有效果呢？ 2016-10-30
- 網(wǎng)站優(yōu)化跟關(guān)鍵詞優(yōu)化有何差異 2014-08-21