#include <iostream>
using namespace std;

template <typename AnyType>
class avltree {
protected:
	class avlnode;
public:
	avltree():root(0),size(0){}
	avltree(const avltree &rhs){
		*this = rhs;
	}
	~avltree()  { 
		cout<<"DESTROY!"<<endl;
		makeEmpty();
		cout<<"OK" ;
		}
	
	const avltree &operator=(const avltree &rhs){
		makeEmpty();
		root = clone(rhs.root);
		return *this;
	}
	/////////////
	long int getSize() const{
		return size;
	}
	/////////////////
	AnyType getData(avlnode *t) const{
		if(t!=0)
			return t->data;
	}
	
	/////////////////////////////////
	int getHeight(avlnode *t) const{
		return (t==0 ? -1 : t->height);
	}

	
	//Insert a specific node into the tree.
  bool insert(const AnyType &x){
		//Insert the avlnode.
		if(root == 0){
			root = new avlnode(x,0,0);
			++size;
			return true;
		}
		int top = 0;
		//This array Used to save the path that had passed.
		avlnode (**upd[HEIGHT_LIMIT]);
		upd[top++] = &root;		
		bool dir;
		while(*upd[top-1] != 0){
			//If x had been in the tree,insert() method return false.
			if(x == (*upd[top-1])->data)
				return false;
			dir = (x > (*upd[top-1])->data);
			upd[top++] = &( (*upd[top-1])->link[dir] );
		}	
		*upd[top-1] = new avlnode(x,0,0);
		++size;
		
		//Rebalance after insert.
		for(int i=top-1; i>=0; --i){
			bool dic1 = x < (*upd[i])->data;					
			//The situations that need to be rotated.
			if( getHeight((*upd[i])->link[!dic1])
						- getHeight((*upd[i])->link[dic1]) ==2 ){
				bool dic2 = x < (*upd[i])->link[!dic1]->data;
				//The single rotation situations.
				if(dic1 == dic2)
					singleRotation(*upd[i],dic2);				
				//The double rotation situations.
				else
					doubleRotation(*upd[i],dic2);
			}
			(*upd[i])->height =max( getHeight((*upd[i])->link[0]),
												  getHeight((*upd[i])->link[1]) )+1;	
		}
		//The new node x had inserted in the tree,and the tree 
		//has been rebalanced,then return true.
		return true;
	}
			
		
	//Remove a specific node of the tree.
	bool remove(const AnyType &x){
		if(root == 0)
			return false;

		avlnode (**upd[HEIGHT_LIMIT]);
		int top = 0;
		upd[top++] = &root;
		
		//Find the position of x.
		while((*upd[top-1])->data != x){
			bool dir = (x > (*upd[top-1])->data);
			upd[top++] = &( (*upd[top-1])->link[dir] );
			//If the tree hasn't the node x,then return false.
			if(*upd[top-1] == 0)
				return false;
		}
		
		//The save indicate the position of x-node,
		//the upd[top-1] now becomes the save's left subtree.
		do{
			if((*upd[top-1])->link[0] == 0 && (*upd[top-1])->link[1] == 0){
				delete *upd[top-1];
				*upd[top-1] = 0;
				top--;
				break;
			}
			
			int save = top-1;
			upd[top] = &( (*upd[top-1])->link[0] );
			top++;
			//Find the largest one of the subtree 
			//whose root is upd[save] (or upd[top-1]).
			while((*upd[top-1])->link[1] != 0)
				upd[top++] = &( (*upd[top-1])->link[1] );
				
		//Delete the avlnode with value x.
			(*upd[save])->data = (*upd[top-1])->data;		
			avlnode *tmp = *upd[top-1];
			cout<<"top="<<top<<endl;
			if(tmp->link[0] == 0){
				*upd[top-1] = 0;
				delete tmp;
				top--;
			}
			else{
				*upd[top-1] = (tmp->link[0]);
				delete tmp;
			}
			cout<<"top="<<top<<endl;
			cout<<"*top["<<(top-1)<<"]="<<(*upd[top-1])->data<<endl;
			size--;
		}while(0);
		//Rebalance after remove.
		for(int i=top-1; i>=0; --i){
			(*upd[i])->height =max( getHeight((*upd[i])->link[0]),
												  getHeight((*upd[i])->link[1]) )+1;
			bool dic1 =( getHeight((*upd[i])->link[0]) 										
									< 
									 getHeight((*upd[i])->link[1]) ); 
			if( getHeight((*upd[i])->link[dic1])
						- getHeight((*upd[i])->link[!dic1]) ==2 ){
				bool dic2 =
				( getHeight( (*upd[i])->link[dic1]->link[0] )
										 		>
					getHeight( (*upd[i])->link[dic1]->link[1] ) );
				//The single rotation situations.
				if(dic1 == dic2)
					singleRotation(*upd[i],dic2);
					
				//The double rotation situations.
				else
					doubleRotation(*upd[i],dic2);
			}
		}
		
	}

	//Destroy the whole tree.
	void makeEmpty(){
		avlnode *it = root;
		avlnode *save;
	
		while(it != 0){
			if(it->link[0] != 0){
				/*Right rotation */
				save = it->link[0];
				it->link[0] = save->link[1];
				save->link[1] = it;
			}
			else{
				save = it->link[1];
				delete it;
			}
			it = save;
		}
	root = 0;
	size = 0;
	}
	
	//Two way single rotation:dir equal to 1 as root_left_left,
	//dir equal to 0 as root_right_right.
	void singleRotation(avlnode* &t, bool dir){
		avlnode *save = t->link[!dir];
		t->link[!dir] = save->link[dir];
		save->link[dir] = t;
		t->height = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		save->height = max( getHeight(save->link[0]),
														getHeight(save->link[1]) ) + 1;		
		t = save;
	}
	
	//Two way double rotation:dir equal to 1 as root_right_left,
	//dir equal to 0 as root_left_right.
	void doubleRotation(avlnode* &t, bool dir){
	  avlnode *s1 = t->link[dir];
	  avlnode *s2 = s1->link[!dir];
	  t->link[dir] = s2->link[!dir];
	  s1->link[!dir] = s2->link[dir];
	  s2->link[dir] = s1;
	  s2->link[!dir] = t;
  	
		s1->height = max( getHeight(s1->link[0]),getHeight(s1->link[1]) ) + 1;		
		t->height  = max( getHeight(t->link[0]),getHeight(t->link[1]) ) + 1;
		s2->height = max( getHeight(s2->link[0]),getHeight(s2->link[1]) ) + 1;
		
		t=s2;
	}
	
	//Inorder trave the tree with a callback op.
 	void printTree() const{
		if(root == 0)
			return;
		avlnode *t = root;
		avlnode *up[HEIGHT_LIMIT];
		int top = 0;
	
		while(1){
			while(t->link[0] != 0){
				up[top++] = t;
				t = t-> link[0];
			}
			cout<<t->data<<'('<<t->height<<')'<<"->";
			while(t->link[1] ==0){
				if(top > 0){
					t = up[--top];
					cout<<t->data<<'('<<t->height<<')'<<"->";
				}
				else
					return;
			}
		t = t->link[1];	
		}
	}
	
	//Return the Max value of int.
	int max(int a,int b){
		return ( a>b ? a : b );
	}
	///////////////////////////
	//
	avlnode *clone(avlnode *t) const{
		if(t==0)
			return t;	
		return new avlnode( t->element,clone(t->link[0]),clone(t->link[1]) );
	}

protected:
	avlnode 		 *root;		// Top of the tree
  long int      size;   // Number of items (user-defined)
  //The tallest of the tree.
  static const int 		HEIGHT_LIMIT = 64;

protected:
  class avlnode 
	{
		explicit avlnode(const AnyType &InitData,avlnode *lt = 0,
				avlnode *rt = 0)
			: height(0),data(InitData){
				link[0] = lt;
				link[1] = rt;
		}
		int          height; 	// height factor
		AnyType        data;  // User-defined content 
		avlnode 	 *link[2]; 	// Left (0) and right (1) links
		friend class avltree;
	};
	
};




int main()
{
	cout<<endl<<endl<<"/*******************/";
	avltree<int> myAVL;

	myAVL.insert(1);
	myAVL.insert(3);
	myAVL.insert(2);
	myAVL.insert(4);
	myAVL.insert(7);
	myAVL.insert(6);
	myAVL.insert(5);	
	myAVL.insert(60);
	myAVL.insert(15);
	myAVL.insert(21);
	myAVL.remove(4);
	myAVL.insert(16);       
	myAVL.insert(37);
	myAVL.insert(14);
	
	myAVL.insert(2);
	myAVL.insert(2);
	myAVL.insert(2);
	myAVL.remove(16);
	
	cout<<endl<<endl;
	myAVL.printTree();
	cout<<endl;
	cout<<endl<<"The size is "<<myAVL.getSize()<<"."<<endl;
	cout<<"After makeEmpty(),";
	myAVL.makeEmpty();
	cout<<"the size is "<<myAVL.getSize()<<"."<<endl;
	cout<<"ok!"<<endl;
	char a;
	cin>>a;

}