#include <iostream>
using namespace std;
typedef int Type;
struct Node{
Type key;
int height;
Node* lchild, *rchild;
Node(){}
Node( int k, int h, Node* l, Node* r ):
key(k), height(h), lchild(l), rchild(r) {}
};
class AVLTree{
private:
Node* _null; // 規(guī)定的空結(jié)點(diǎn)
Node* root; // 根結(jié)點(diǎn)
void left_single_rotate( Node*& r ); // 左單旋轉(zhuǎn)
void left_double_rotate( Node*& r ); // 左雙旋轉(zhuǎn)
void right_single_rotate( Node*& r ); // 右單旋轉(zhuǎn)
void right_double_rotate( Node*& r ); // 右雙旋轉(zhuǎn)
void erase_rotate_help( Node*& r ); // 刪除操作中的旋轉(zhuǎn)
void travel( int, Node* root ); // 遍歷樹(shù)
void insert_help( Node*& r, Type key ); // 插入
void erase_help ( Node*& r, Type key ); // 刪除
public:
AVLTree(){ _null= new Node( 0, 0, NULL, NULL ); root= _null; }
void travel(); // 遍歷樹(shù)
void insert( Type key ); // 插入數(shù)據(jù)
void erase ( Type key ); // 刪除數(shù)據(jù)
};
// 左單旋轉(zhuǎn)實(shí)現(xiàn)
void AVLTree::left_single_rotate( Node*& r ){
Node* tmp= r->rchild;
r->rchild= tmp->lchild;
r->height= max( r->lchild->height, r->rchild->height )+ 1;
tmp->lchild= r; r= tmp;
r->height= max( r->lchild->height, r->rchild->height )+ 1;
}
// 右單旋轉(zhuǎn)實(shí)現(xiàn)
void AVLTree::right_single_rotate( Node*& r ){
Node* tmp= r->lchild;
r->lchild= tmp->rchild;
r->height= max( r->lchild->height, r->rchild->height )+ 1;
tmp->rchild= r; r= tmp;
r->height= max( r->lchild->height, r->rchild->height )+ 1;
}
// 左雙旋轉(zhuǎn)實(shí)現(xiàn)
void AVLTree::left_double_rotate( Node*& r ){
right_single_rotate( r->rchild );
left_single_rotate( r );
}
// 右雙旋轉(zhuǎn)實(shí)現(xiàn)
void AVLTree::right_double_rotate( Node*& r ){
left_single_rotate( r->lchild );
right_single_rotate( r );
}
void AVLTree::travel( int parent, Node* r ){
if( r!= _null ){
travel( r->key, r->lchild );
cout << parent << ' ' << r->key << ' ' << r->height << endl;
travel( r->key, r->rchild ); }
}
void AVLTree::travel(){
travel( -1, root ); }
void AVLTree::insert_help( Node*& r, Type key ){
if( r== _null ){
r= new Node( key, 1, _null, _null );
return; }
if( key< r->key ) insert_help( r->lchild, key );
else insert_help( r->rchild, key );
// 這上面一部分同二叉查找樹(shù)的代碼 ,AVL樹(shù)只是在其基礎(chǔ)上
// 增加了旋轉(zhuǎn)保持平衡的操作
// 調(diào)整根結(jié)點(diǎn)的高度，因?yàn)樵黾咏Y(jié)點(diǎn)后，高度可能增加
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 如果右子樹(shù)不為空
if( r->rchild!= _null ){
// 左子樹(shù)的高度加上1等于右子樹(shù)的右子樹(shù)的高度，則左單旋轉(zhuǎn)
if( r->lchild->height+ 1== r->rchild->rchild->height )
left_single_rotate( r );
// 左子樹(shù)的高度加上1等于右子樹(shù)的左子樹(shù)的高度，則左雙旋轉(zhuǎn)
else if( r->lchild->height+ 1== r->rchild->lchild->height )
left_double_rotate( r );
}
// 如果左子樹(shù)不為空
if( r->lchild!= _null ){
// 右子樹(shù)的高度加上1等于左子樹(shù)的左子樹(shù)的高度，則右單旋轉(zhuǎn)
if( r->rchild->height+ 1== r->lchild->lchild->height )
right_single_rotate( r );
// 右子樹(shù)的高度加上1等于左子樹(shù)的右子樹(shù)的高度，則右雙旋轉(zhuǎn)
else if( r->rchild->height+ 1== r->lchild->rchild->height )
right_double_rotate( r );
}
}
void AVLTree::insert( Type key ){
insert_help( root, key ); }
void AVLTree::erase_rotate_help( Node*& r ){
// 右子樹(shù)高度比左子樹(shù)高度大2
if( r->rchild->height- r->lchild->height== 2 ){
// 如果右子樹(shù)的左子樹(shù)的高度不大于右子樹(shù)的右子樹(shù)的高度則對(duì)根左單旋轉(zhuǎn)
if( r->rchild->lchild->height<= r->rchild->rchild->height )
left_single_rotate( r );
// 如果右子樹(shù)的左子樹(shù)的高度大于右子樹(shù)的右子樹(shù)的高度則對(duì)根左雙旋轉(zhuǎn)
else
left_double_rotate( r );
}
// 左子樹(shù)高度比右子樹(shù)高度大2
else if( r->lchild->height- r->rchild->height== 2 ){
// 如果左子樹(shù)的右子樹(shù)的高度不大于左子樹(shù)的左子樹(shù)的高度則對(duì)根右單旋轉(zhuǎn)
if( r->lchild->rchild->height<= r->lchild->lchild->height )
right_single_rotate( r );
// 如果左子樹(shù)的右子樹(shù)的高度大于左子樹(shù)的左子樹(shù)的高度則對(duì)根右雙旋轉(zhuǎn)
else
right_double_rotate( r );
}
}
void AVLTree::erase_help( Node*& r, Type key ){
if( r== _null ) return; // 沒(méi)有找到要?jiǎng)h除的結(jié)點(diǎn)則直接退出
if( r->key== key ){
if( r->rchild== _null ){
Node* tmp= r;
r= r->lchild; delete tmp;
}
else {
Node* tmp= r->rchild;
while( tmp->lchild!= _null ) tmp= tmp->lchild;
r->key= tmp->key;
erase_help( r->rchild, tmp->key );
r->height= max( r->lchild->height, r->rchild->height )+ 1;
}
return ; }
if( key< r->key ) erase_help( r->lchild, key );
else erase_help( r->rchild, key );
// 同樣，這上面一部分同二叉查找樹(shù)的代碼 ,AVL樹(shù)只是在其基礎(chǔ)上
// 增加了旋轉(zhuǎn)保持平衡的操作
// 調(diào)整高度
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 有可能在左子樹(shù)中把結(jié)點(diǎn)刪除導(dǎo)致左子樹(shù)不平衡
// 故先檢測(cè)左子樹(shù)是否已經(jīng)平衡，否 則調(diào)整
if( r->lchild!= _null ) erase_rotate_help( r->lchild );
// 同樣右子樹(shù)中也有可能不平衡，檢測(cè)右子樹(shù)并調(diào)整
if( r->rchild!= _null ) erase_rotate_help( r->rchild );
// 檢測(cè)根并調(diào)整
erase_rotate_help( r );
}
void AVLTree::erase( Type key ){
erase_help( root, key ); }
int main(){
AVLTree test;
freopen("a.txt","w",stdout);
for( int i= 0; i< 100000; ++i )
if( i& 1 ) test.insert( rand() );
else test.erase ( rand() );
test.travel();
return 0;
}
posted on 2009-05-07 22:03
Darren 閱讀(2612)
評(píng)論(6) 編輯 收藏 引用