#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

#define MAXH 30		//define max hight of the tree
//#define Win

/*
define a KeyType and it`s basic arithmetics
*/
typedef int KeyType;
bool LessT(KeyType k1, KeyType k2){return k1<k2;}
bool Equal(KeyType k1, KeyType k2){return k1==k2;}

#ifndef __GNUC__
template< typename T>
inline T max(T x,T y){return x>y?x:y;}
#endif

/*
define hight relation
*/
#define LTH 1
#define EQH 0
#define RTH -1

/*
define an AVL node
*/
class node{
public:
	KeyType key;
	int bf; //balance factor
	node * leftch, * rightch;
	node(){
		leftch=rightch=NULL;
		bf=0;
	}
	node(KeyType kv){
		leftch=rightch=NULL;
		bf=0;
		key=kv;
	}
};


/************************************************************************/
/* define a balanced binary search tree                                 */
/************************************************************************/
class AVLTree{
protected:
	node *stk[MAXH];//use a stack to store visited node
	int dir[MAXH];	//1, left ; -1, right
	int top;
	void adjustTreeAfterInsert();
	bool adjustTreeAfterDelete();
	void RRotate(node * &rt);
	void LRotate(node * &rt);
	bool search(KeyType kv);
public:
	int tnn;		//total node number
	node *root;
	AVLTree();
	AVLTree(KeyType k[], int n);
	bool insert(KeyType kv);
	bool erase(KeyType kv);
	void query(KeyType kv);
	void prtTree();
	void prtASL();
};


/************************************************************************/
/* define a binary search tree                                          */
/************************************************************************/
class BSTree{
public:
	node *root;
	int tnn;
	BSTree();
	BSTree(KeyType k[], int n);
	bool insert(KeyType kv);
	bool erase(KeyType kv);
	void delNode(node * &rt);
	void query(KeyType kv);
	void prtTree();
	void prtASL();
};

/*
define Global Functions
*/
void InOrderTrav(node *, bool);
int totSearchLength(node *,int);
void delTree(node * &);

#include "AVL.h"

/************************************************************************/
/* Global Functions                                                     */
/************************************************************************/
/*
	in order traverse of a tree
	parameter: tree root, show balance factor
*/
void InOrderTrav(node *rt, bool sbf){
    if(rt==NULL)
		return;
    InOrderTrav(rt->leftch,sbf);
    if(sbf) cout<<rt->key<<' '<<rt->bf<<"\t";
    else    cout<<rt->key<<"\t";
    InOrderTrav(rt->rightch,sbf);
}

void PreOrderTrav(node *rt, bool sbf, int lev){
    if(rt==NULL)
		return;
    if(sbf) cout<<rt->key<<' '<<rt->bf<<"\t"<<lev<<endl;
    else    cout<<rt->key<<"\t";
	PreOrderTrav(rt->leftch,sbf,lev+1);
    PreOrderTrav(rt->rightch,sbf,lev+1);
}

/*
*	count out the sum of search length for each node
*	in the tree
*/
int totSearchLength(node *rt,int level){
	int len=level;
	if(rt->leftch)
		len+=totSearchLength(rt->leftch,1+level);
	if(rt->rightch)
		len+=totSearchLength(rt->rightch,1+level);
	return len;
}

/*
*	delete the hole Tree
*/
void delTree(node * &rt){
	if(rt->leftch) 
		delTree(rt->leftch);
	if(rt->rightch)
		delTree(rt->rightch);
	delete rt;
	rt=NULL;
}

/************************************************************************/
/* Functions in AVL Tree                                                */
/************************************************************************/
void AVLTree::adjustTreeAfterInsert(){
	int p=top;
	node * &rp = p==0?(root):(dir[p-1]>0 ? stk[p-1]->leftch : stk[p-1]->rightch);
    cout<<"Adjust unbalenced tree after insertion"<<endl;
    if(dir[p]>0){
		node * &rc=dir[p]>0 ? stk[p]->leftch : stk[p]->rightch;
        if(dir[p+1]<0){
            LRotate(rc);
        }
        RRotate(rp);
    }
    else{
		node * &lc=dir[p]>0 ? stk[p]->leftch : stk[p]->rightch;
        if(dir[p+1]>0){
            RRotate(lc);
        }
        LRotate(rp);
    }
}

/*
*	return true if AVL tree is balanced and no more adjust is needed,
*	else return false.
*	now stk[top] indicate the top of the stack exactly
*/
bool AVLTree::adjustTreeAfterDelete(){
	int p=top;
	node * &rp = p==0?(root):(dir[p-1]>0 ? stk[p-1]->leftch : stk[p-1]->rightch);
	cout<<"Adjust unbalenced tree after deletion"<<endl;
	if(stk[p]->bf < 0){	//right high
		node * &rc=stk[p]->rightch;
		switch(rc->bf){
		case RTH:
			LRotate(rp);
			return false;
		case EQH:
			LRotate(rp);
			return true;
		case LTH:
			RRotate(rc);
			LRotate(rp);
			return false;
		}
	}
	else {	//left high
		node * &lc=stk[p]->rightch;
		switch(lc->bf){
		case LTH:
			RRotate(rp);
			return false;
		case EQH:
			RRotate(rp);
			return true;
		case RTH:
			LRotate(lc);
			RRotate(rp);
			return false;
		}
	}
	return true;
}

void AVLTree::RRotate(node* &A){
    node * B  = A->leftch;
    A->leftch = B->rightch;
    B->rightch= A;
    int blh=B->bf;
    int brh=0;
    int arh=max(blh,0)+1-A->bf;
    A->bf=brh-arh;
    B->bf=blh-max(brh,arh)-1;
    A=B;
}

void AVLTree::LRotate(node * &A){
    node * B   = A->rightch;
    A->rightch = B->leftch;
    B->leftch  = A;
    int blh=B->bf;
    int brh=0;
    int alh=max(blh,0)+1+A->bf;
    A->bf=alh-blh;
    B->bf=max(alh,blh)+1-brh;
    A=B;
}

/*
*	search node with key, var top gives the number of visited nodes
*	return true if search success, the top of the stack is the pointer points to the
*		node with given key, and the top element of dir[] is useless
*   return false if search failed, the top of the stack is the pointer points to the
*		leaf node where a new with that key can be attached to
*/
bool AVLTree::search(KeyType kv){
	node *np=root;
	bool res=false;
	top=0;			//set stack empty
	if(root==NULL){	//empty tree
		return false;
    }
	while(np && !res){
		stk[top]=np;
		if(LessT(kv, np->key)){
			np=np->leftch;
			dir[top]=1;
		}
		else if(Equal(kv, np->key)){
			res = true;
		}
		else {
			np=np->rightch;
			dir[top]=-1;
		}
		top++;
	}
	return res;
}

AVLTree::AVLTree(){
    root=NULL;tnn=0;
	cout<<"Construct an empty AVL tree"
		<<endl<<endl;
}

AVLTree::AVLTree(KeyType k[], int n){
    root=NULL;tnn=n;
    int i;
    for(i=0;i<n;i++){
        insert(k[i]);
    }
	cout<<"construct a new AVL tree with "<<n<<" nodes"
		<<endl<<endl;
}

/*
*	return true if insertion succeed
*	else return false
*/
bool AVLTree::insert(KeyType kv){
	if(search(kv)) return false;    //seach success, exist a node with same key
	node *nn=new node(kv);
	top--;
	if(top<0) {
		node *nn=new node(kv);
        cout<<"Create AVL root node"<<endl;
        root=nn;
		return true;
	}
	if(dir[top]>0)stk[top]->leftch =nn;
	else          stk[top]->rightch=nn;
	for(;top>=0;top--){
		stk[top]->bf += dir[top];
		switch((int)fabs(stk[top]->bf)){
		case 0:	//no need to do further modification
            return true;
		case 1:	//continue;
			break;
		case 2:	//adjust now
            adjustTreeAfterInsert();
			return true;
		}
	}
	return true;
}

/*
*	return true if deletion succeed
*	else return false
*/
bool AVLTree::erase(KeyType kv){
	cout<<"Delete key "<<kv<<" in AVL:"<<endl;
	if(!search(kv)) {
		cout<<"Can not find node with the same key, deletion failed."<<endl;
		return false;
	}
	dir[top-1]=1;
	node *th = stk[top-1]->leftch;
	for(; th; th=th->leftch){
		stk[top]=th;
		dir[top]=1;
		stk[top-1]->key=th->key;
		top++;
	}

	th=stk[top-1];
	if(th->rightch){	//left most node have a right child
		node * & rc=th->rightch;
		top--;
		(top>0?stk[top-1]->key:root->key) = rc->key;
		delete rc;
		rc=NULL;
		th->bf=0;
	}
	else {
		delete th;
		top--;
		(top>0 ? (dir[top-1]>0 ? stk[top-1]->leftch : stk[top-1]->rightch) : root) = NULL;
	}

	for(top--; top>=0; top--){
		stk[top]->bf -= dir[top];
		switch(stk[top]->bf){
		case 0:
			break;
		case 1:
		case -1:
			return true;
		case 2:
		case -2:
			if(adjustTreeAfterDelete())
				return true;
			break;
		}
	}
	return true;
}

void AVLTree::query(KeyType kv){
	cout<<"In AVL, ";
	if(search(kv))
		cout<<"find node with search length "<<top<<endl;
	else 
		cout<<"cannot find node with the same key"<<endl
		<<"Query failed"<<endl;
}

void AVLTree::prtTree(){
	cout<<"In order traverse of AVL tree:"<<endl;
	InOrderTrav(root, 1);
	cout<<endl
		<<tnn<<" node(s) in all"
		<<endl<<endl;
}

void AVLTree:: prtASL(){
	cout<<"Average search length of AVL tree: "
		<<((double)totSearchLength(root, 1)/tnn)
		<<endl<<endl;
}

/************************************************************************/
/* Functions in BST Tree                                                */
/************************************************************************/

BSTree::BSTree(){
	root=NULL;tnn=0;
	cout<<"Construct an empty BST tree"
		<<endl<<endl;
}
BSTree::BSTree(KeyType k[], int n){
	root=NULL;tnn=n;
	int i;
	for(i=0;i<n;i++){
		insert(k[i]);
	}
	cout<<"Construct a new BST tree with "<<n<<" nodes"
		<<endl<<endl;
}

/*
*	return true if insertion succeed
*	else return false
*/
bool BSTree::insert(KeyType kv){
	node *np=root, *last;
	int dir, cnt=0;
	//cout<<"Insert new node with key "<<kv<<endl;
	if(root==NULL){//empty tree
		node *nn=new node(kv);
		cout<<"Create BST root node."<<endl;
		root=nn;
		return true;
	}
	while(np){
		last=np;
		if(LessT(kv, np->key)){
			np=np->leftch;
			dir=1;
		}
		else if(Equal(kv, np->key)){
			//cout<<"Identical key found, insertion failed"<<endl;
			return false;
		}
		else {
			np=np->rightch;
			dir=-1;
		}
		cnt++;
	}
	//cout<<"find insert position after searching "<<cnt<<" nodes"<<endl;
	node *nn=new node(kv);
	if(dir>0)last->leftch =nn;
	else     last->rightch=nn;
	return true;
}

void BSTree::query(KeyType kv){
	int cnt=0;
	node *np=root;
	while(np){
		cnt++;
		if(LessT(kv,np->key))
			np=np->leftch;
		else if(Equal(kv, np->key))
			break;
		else
			np=np->rightch;
	}
	cout<<"In BST, ";
	if(np==NULL)
		cout<<"cannot find node with the same key"<<endl
			<<"Query failed"<<endl;
	else {
		cout<<"find node with search length "<<cnt<<endl;
	}
}

/*
*	return true if deletion succeed
*	else return false
*/
bool BSTree::erase(KeyType kv){
	node *np=root, *lt; int dir;
	cout<<"Delete key "<<kv<<" in BST:"<<endl;
	if(root==NULL){
		cout<<"Empty tree, can not delete node"<<endl;
		return false;
	}
	if(root->key==kv) {
		delNode(root);
		cout<<"Delete root node"<<endl;
		return true;
	}
	while(np){
		if(Equal(kv, np->key)){
			delNode (dir>0 ? lt->leftch : lt->rightch);
			cout<<"Delete node success"<<endl;
			return true;
      		}
		else {
			lt=np;
			if(LessT(kv,np->key)){
				np=np->leftch;
				dir=1;
			}
			else {
				np=np->rightch;
				dir=-1;
			}
		}
	}
	cout<<"cannot find node with the same key. Deletion failed"<<endl;
	return false;
}

void BSTree::delNode(node * &rt){
	node *td=rt;
	if(rt->leftch && rt->rightch){//none of two children is empty
		node *lm=rt->leftch;			//left maximum node
		while(lm->rightch)
			lm=lm->rightch;
		lm->rightch=rt->rightch;
		rt=rt->leftch;
	}
	else if(rt->leftch){    //right child is empty
		rt=rt->leftch;
	}
	else if(rt->rightch){   //left child is empty
		rt=rt->rightch;
   	}
	else {					//both children are empty
		rt=NULL;
	}
	delete td;
}

void BSTree::prtTree(){
	if(root==NULL){
		cout<<"Empty tree."<<endl;
		return;
	}
	cout<<"In order traverse of BST tree:"<<endl;
	InOrderTrav(root, 0); 
	cout<<endl
		<<tnn<<" node(s) in all"
		<<endl<<endl;
}

void BSTree::prtASL(){
	cout<<"Average search length of BST tree: "
		<<( (double)totSearchLength(root, 0)/tnn )
		<<endl<<endl;
}

const int maxl=50000;
KeyType k[maxl/10];
char buf[maxl];
int i;
#define DEB
int cmp(int a, int b){
	return a%10 < b%10;
}

int main(int argc, char *argv[])
{
    int N=0;
	/*
    cin.getline(buf,maxl);
    */
	//freopen("avl.out","w",stdout);
	
    FILE *fp=fopen("avl.in","r");
	fgets(buf,maxl,fp);
    
	istringstream dig(buf);
	while(dig>>k[N]) N++;
	
	/*
	k[0]=10;
	k[1]=5;
	k[2]=15;
	k[3]=8;
	N=2;
	*/
	//cout<<endl<<"Input sequence: ";for(int i=0;i<N;i++)cout<<k[i]<<" ";cout<<endl;
	cout<<"Number of sequence element: "<<N<<endl;

    AVLTree balTr(k,N);
    BSTree binTr(k,N);

	balTr.prtTree();
	balTr.prtASL();
	binTr.prtASL();

#ifdef DEB
	sort(k,k+N,cmp);
	PreOrderTrav(balTr.root, 1, 1);cout<<endl<<endl;
	for(i=0;i<N;i++){
		balTr.erase(k[i]);
		PreOrderTrav(balTr.root, 1, 1);cout<<endl<<endl;
		//balTr.prtTree();
	}
	system("PAUSE");
	return 0;
#endif

    string cmd;
    KeyType kv;
    while(1){
#ifdef Win
        system("PAUSE");
        system("cls");
#endif
        cout<<"Input format :(case NOT matter)"<<endl
            <<"Insert [key_value]"<<endl
            <<"Delete [key_value]"<<endl
            <<"Query  [key_value]"<<endl
            <<"Print  AVL/BST"<<endl
            <<"ASL    AVL/BST"<<endl
            <<"Exit"<<endl<<endl;
        cin>>cmd;
        if(tolower(cmd[0])=='e'){
            break;
        }
        else 
        switch(tolower(cmd[0])){
            case 'i':
				cin>>kv;
                if(balTr.insert(kv)) balTr.tnn++;
                if(binTr.insert(kv)) binTr.tnn++;
                break;
            case 'd':
				cin>>kv;
                if(binTr.erase(kv)) binTr.tnn--;
                if(balTr.erase(kv)) balTr.tnn--;
                break;
            case 'q':
				cin>>kv;
                balTr.query(kv);
                binTr.query(kv);
                break;
            case 'p':
				cin>>cmd;
				if(tolower(cmd[0])=='a'){
					PreOrderTrav(balTr.root, 1, 1);cout<<endl<<endl;
					balTr.prtTree();
				}
				else
	            binTr.prtTree();
	            break;
	        case 'a':
				cin>>cmd;
				if(tolower(cmd[0])=='a')
	            balTr.prtASL();
	            else
	            binTr.prtASL();
	            break;
            default:
                cout<<"Invalid commander!";
                break;
        }
    }
    return EXIT_SUCCESS;
}

• 我都调试一整天了...... (0) qiqilrq 2007-09-11 02:02:22