#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 ); // 遍歷樹
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(); // 遍歷樹
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 );
// 這上面一部分同二叉查找樹的代碼 ,AVL樹只是在其基礎(chǔ)上
// 增加了旋轉(zhuǎn)保持平衡的操作
// 調(diào)整根結(jié)點(diǎn)的高度，因?yàn)樵黾咏Y(jié)點(diǎn)后，高度可能增加
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 如果右子樹不為空
if( r->rchild!= _null ){
// 左子樹的高度加上1等于右子樹的右子樹的高度，則左單旋轉(zhuǎn)
if( r->lchild->height+ 1== r->rchild->rchild->height )
left_single_rotate( r );
// 左子樹的高度加上1等于右子樹的左子樹的高度，則左雙旋轉(zhuǎn)
else if( r->lchild->height+ 1== r->rchild->lchild->height )
left_double_rotate( r );
}
// 如果左子樹不為空
if( r->lchild!= _null ){
// 右子樹的高度加上1等于左子樹的左子樹的高度，則右單旋轉(zhuǎn)
if( r->rchild->height+ 1== r->lchild->lchild->height )
right_single_rotate( r );
// 右子樹的高度加上1等于左子樹的右子樹的高度，則右雙旋轉(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 ){
// 右子樹高度比左子樹高度大2
if( r->rchild->height- r->lchild->height== 2 ){
// 如果右子樹的左子樹的高度不大于右子樹的右子樹的高度則對根左單旋轉(zhuǎn)
if( r->rchild->lchild->height<= r->rchild->rchild->height )
left_single_rotate( r );
// 如果右子樹的左子樹的高度大于右子樹的右子樹的高度則對根左雙旋轉(zhuǎn)
else
left_double_rotate( r );
}
// 左子樹高度比右子樹高度大2
else if( r->lchild->height- r->rchild->height== 2 ){
// 如果左子樹的右子樹的高度不大于左子樹的左子樹的高度則對根右單旋轉(zhuǎn)
if( r->lchild->rchild->height<= r->lchild->lchild->height )
right_single_rotate( r );
// 如果左子樹的右子樹的高度大于左子樹的左子樹的高度則對根右雙旋轉(zhuǎn)
else
right_double_rotate( r );
}
}
void AVLTree::erase_help( Node*& r, Type key ){
if( r== _null ) return; // 沒有找到要刪除的結(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 );
// 同樣，這上面一部分同二叉查找樹的代碼 ,AVL樹只是在其基礎(chǔ)上
// 增加了旋轉(zhuǎn)保持平衡的操作
// 調(diào)整高度
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 有可能在左子樹中把結(jié)點(diǎn)刪除導(dǎo)致左子樹不平衡
// 故先檢測左子樹是否已經(jīng)平衡，否 則調(diào)整
if( r->lchild!= _null ) erase_rotate_help( r->lchild );
// 同樣右子樹中也有可能不平衡，檢測右子樹并調(diào)整
if( r->rchild!= _null ) erase_rotate_help( r->rchild );
// 檢測根并調(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 閱讀(2603)
評論(6) 編輯 收藏 引用