#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; // 規定的空結點
Node* root; // 根結點
void left_single_rotate( Node*& r ); // 左單旋轉
void left_double_rotate( Node*& r ); // 左雙旋轉
void right_single_rotate( Node*& r ); // 右單旋轉
void right_double_rotate( Node*& r ); // 右雙旋轉
void erase_rotate_help( Node*& r ); // 刪除操作中的旋轉
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 ); // 插入數據
void erase ( Type key ); // 刪除數據
};
// 左單旋轉實現
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;
}
// 右單旋轉實現
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;
}
// 左雙旋轉實現
void AVLTree::left_double_rotate( Node*& r ){
right_single_rotate( r->rchild );
left_single_rotate( r );
}
// 右雙旋轉實現
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樹只是在其基礎上
// 增加了旋轉保持平衡的操作
// 調整根結點的高度，因為增加結點后，高度可能增加
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 如果右子樹不為空
if( r->rchild!= _null ){
// 左子樹的高度加上1等于右子樹的右子樹的高度，則左單旋轉
if( r->lchild->height+ 1== r->rchild->rchild->height )
left_single_rotate( r );
// 左子樹的高度加上1等于右子樹的左子樹的高度，則左雙旋轉
else if( r->lchild->height+ 1== r->rchild->lchild->height )
left_double_rotate( r );
}
// 如果左子樹不為空
if( r->lchild!= _null ){
// 右子樹的高度加上1等于左子樹的左子樹的高度，則右單旋轉
if( r->rchild->height+ 1== r->lchild->lchild->height )
right_single_rotate( r );
// 右子樹的高度加上1等于左子樹的右子樹的高度，則右雙旋轉
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 ){
// 如果右子樹的左子樹的高度不大于右子樹的右子樹的高度則對根左單旋轉
if( r->rchild->lchild->height<= r->rchild->rchild->height )
left_single_rotate( r );
// 如果右子樹的左子樹的高度大于右子樹的右子樹的高度則對根左雙旋轉
else
left_double_rotate( r );
}
// 左子樹高度比右子樹高度大2
else if( r->lchild->height- r->rchild->height== 2 ){
// 如果左子樹的右子樹的高度不大于左子樹的左子樹的高度則對根右單旋轉
if( r->lchild->rchild->height<= r->lchild->lchild->height )
right_single_rotate( r );
// 如果左子樹的右子樹的高度大于左子樹的左子樹的高度則對根右雙旋轉
else
right_double_rotate( r );
}
}
void AVLTree::erase_help( Node*& r, Type key ){
if( r== _null ) return; // 沒有找到要刪除的結點則直接退出
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樹只是在其基礎上
// 增加了旋轉保持平衡的操作
// 調整高度
r->height= max( r->lchild->height, r->rchild->height )+ 1;
// 有可能在左子樹中把結點刪除導致左子樹不平衡
// 故先檢測左子樹是否已經平衡，否 則調整
if( r->lchild!= _null ) erase_rotate_help( r->lchild );
// 同樣右子樹中也有可能不平衡，檢測右子樹并調整
if( r->rchild!= _null ) erase_rotate_help( r->rchild );
// 檢測根并調整
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 閱讀(2618)
評論(6) 編輯 收藏 引用