//this is avl tree node 



template <class T> class avlNode//平衡二叉樹結點類
{
	public:
		avlNode(T val);//構造函數
		avlNode(T val,avlNode<T> *left,avlNode<T> *right,int bf);
		avlNode<T>* copy()const;//復制以當前結點為根的二叉樹 ：(寫多了，沒用上)                           
		void release();//刪除以當前結點為根的左右子樹									
		void left(avlNode *);//把當前結點的左指針修改為函數的參數
		avlNode<T>* left()const;//左子結點訪問，返回左結點的指針
		void right(avlNode *v);//把當前結點的右指針修改為函數的參數
		avlNode<T>* right()const;//右子結點訪問，返回右結點的指針
		int add(avlNode<T>* &p,T val);//插入一個值；返回新的avl樹的根結點的指針
		void preorderview(avlNode<T> *current,int i=-1);//前序周游
		avlNode<T>* remove(T val,avlNode<T>* &waste,int &flag);//刪除以當前結點的為根的avl樹中的val結點
		avlNode<T>* findNodeValue(T val);//查找val結點
		T value;//碼值
	private:
		int bf;// balance factor
		avlNode<T>* leftptr;//左右指針
		avlNode<T>* rightptr;
		//avlNode<T>* restoreLeftBalance(int oldbf);//刪除時左子樹失衡的時候調整，返回新的樹根的指針
		//avlNode<T>* restoreRightBalance(int oldbf);//刪除時右子樹失衡的時候調整，返回新的樹根的指針
		avlNode<T>* removeLeftmostElement(avlNode<T>* &childptr,int &flag);//找到最左的結點
		//avlNode<T>* removeBalanceLeft();//從左子樹刪除的時候判斷層數的改變
		//avlNode<T>* removeBalanceRight();//從右子樹刪除的時候判斷層數的改變
		avlNode<T>* LL_singleRotation();//在插入時候左子樹LL失衡的時候調整，返回新的樹根的指針
		avlNode<T>* RR_singleRotation();//在插入時候右子樹RR失衡的時候調整，返回新的樹根的指針
		avlNode<T>* LR_doubleRotation();//在插入時候左子樹LR失衡的時候調整，返回新的樹根的指針
		avlNode<T>* RL_doubleRotation();//在插入時候右子樹RL失衡的時候調整，返回新的樹根的指針
	
};


template <class T> avlNode<T>::avlNode(T val)
{
	value=val;
	leftptr=NULL;
	rightptr=NULL;
	bf=0;
}
template <class T> avlNode<T>::avlNode(T val,avlNode<T> *left,avlNode<T> *right,int bf=0)
{
	value=val;
	leftptr=left;
	rightptr=right;
	bf=bf;
}
template <class T> avlNode<T>* avlNode<T>::copy()const
{
	avlNode<T> *nl,*nr;
	nl=(leftptr==NULL?NULL:leftptr->copy());//遞歸調用復制左子樹
	nr=(rightptr==NULL?NULL:rightptr->copy());//遞歸調用復制右子樹
	avlNode<T>* node=new avlNode<T>(value,nl,nr,bf);
	if(node!=NULL)   //?? ==NULL
		cout<<"error"<<endl;
	else
		return node;
}
template <class T> void avlNode<T>::release()
{
	if (leftptr)
	{//刪除左子樹中的結點
		leftptr->release();//遞歸調用
		delete leftptr;
		leftptr=0;
	}
	if (rightptr)
	{//刪除右子樹中的結點
		rightptr->release();//遞歸調用
		delete rightptr;
		rightptr=0;
	}
}
template <class T> avlNode<T>* avlNode<T>::left()const
{
	return leftptr;
}
template <class T> void avlNode<T>::left(avlNode<T>* v)
{
	leftptr=v;
}
template <class T> avlNode<T>* avlNode<T>::right()const
{
	return rightptr;
}
template <class T> void avlNode<T>::right(avlNode<T>* v)
{
	rightptr=v;
}
template <class T> int avlNode<T>::add(avlNode<T>* &rp,T val)
{//返回值表明以當前結點為根的樹是否再插入之后增高，0:非增高，非0:增高
	if (val<value)
	{//左子樹插入
		if (rp->left()==NULL)
			rp->left(new avlNode<T>(val));
		else if(rp->left()->add(rp->leftptr,val)==0)//插入后子樹沒有增高
			return 0;
		if (rp->bf==-1)
		{//原來已經傾斜，左邊失衡，需要做平衡處理
	       if (rp->left()->bf<0)  //插入在左側，單旋轉
	             rp = LL_singleRotation();
	       else rp = LR_doubleRotation();	//插入在右側，雙旋轉
		   return 0;
		}
		return --bf;   // bf=(0, +1)的情況，不需要調整樹，只要修改bf
	}
	else
	{
		if (rp->right()==NULL)
			rp->right(new avlNode<T>(val));
		else if (rp->right()->add(rp->rightptr,val)==0)//插入后子樹沒有增高 
			return 0;
		if(rp->bf==1)
		{//原來已經傾斜，需要做平衡處理
	       if (rp->right()->bf>0)    //插入在右側，單旋轉
	           rp = RR_singleRotation();
	       else rp = RL_doubleRotation();  //插入點在右側.雙旋轉
		   return 0;
		}
		return ++bf; // bf=(0, -1)的情況，不需要調整樹，只要修改bf
	}
}


template <class T> avlNode<T>* avlNode<T>::remove(T val,avlNode<T>* &waste,int &flag)
{
	if (val==value)
	{
		waste=this;
		//當沒有右子樹的時候返回左子樹
		if(right()==NULL)
		{
			flag=1;
			return left();
		}
		//刪除右子樹中的最小結點
		int oldbf=right()->bf;
		avlNode* newroot;
		right(right()->removeLeftmostElement(newroot,flag));//找到后返回已經平衡的avl樹的根指針
		newroot->left(left());
		newroot->right(right());
		if((flag==1)&&(bf==1))
			flag=1;
		else flag=0;
		if(flag==1)
		{
			newroot->bf=bf--;
		}
		else newroot->bf=bf;
        //左樹的平衡
		avlNode<T>* rightchild=newroot->right();
	    if (rightchild==NULL) 
		    bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		    bf--;
    	if (bf<-1)
		{
		    int newoldbf=newroot->left()->bf;
	        if (newoldbf>0)
			{//雙旋轉
    	       return newroot->LR_doubleRotation();
			}
	        else
			{//單旋轉
		       return newroot->LL_singleRotation();
           	}
		}
	    return newroot;
		
	}
	else if(val<value)
	{//從左子樹中刪除
		if(left()==NULL)
			return this;
		//執行刪除
		int oldbf=left()->bf;
		left(left()->remove(val,waste,flag));//遞歸調用
        //調整左子樹
        avlNode<T>* leftchild=left();
	//	if(flag==1)
	//		bf++;
	    //計算刪除后的子樹對當前的根結點的平衡因子的影響
	    if (leftchild==NULL)
		   bf++;
	    else if((leftchild->bf!=oldbf)&&(leftchild->bf==0))
		   bf++;
	    if (bf>1)//失衡
		{//調整
		   int newoldbf=right()->bf;
	       if (newoldbf<0)//雙旋轉
		   {
	           return RL_doubleRotation();
		   }
	       else
		   {//單旋轉
		       avlNode* temp= RR_singleRotation();
			   if(flag==1)
				   bf++;
			   return temp;
		   }
		}
    	return this;
	}
	else
	{//從右子樹中刪除
		if(right()==NULL)
			return this;
		//執行刪除
		int oldbf=right()->bf;
		right(right()->remove(val,waste,flag));//遞歸調用
		//調整右子樹
		avlNode<T>* rightchild=right();
    	if (rightchild==NULL) 
		  bf--;
	    else if((rightchild->bf!=oldbf)&&(rightchild->bf==0))
		  bf--;
	    if (bf<-1)
		{
		  int newoldbf=left()->bf;
	      if (newoldbf>0)
		  {//雙旋轉
    	      return LR_doubleRotation();
		  }
	      else
		  {//單旋轉
			  avlNode* temp= LL_singleRotation();
			  if(flag==1)
			    bf--;
			   return temp;
		   }
		} 
	    return this;
	}
}

template <class T> avlNode<T>* avlNode<T>::removeLeftmostElement(avlNode<T>* &childptr,int &flag)
{//flag 表示子樹高度是否變化
	avlNode* leftchild=left();
	//找到最小的值，返回，否則遞歸調用
	if (leftchild==NULL)
	{
		childptr=this;
		flag=1;
		return right();
	}
	int oldbf=leftchild->bf;
	left(leftchild->removeLeftmostElement(childptr,flag));//遞歸調用
	//調整左子樹平衡
	avlNode<T>* newleftchild=left();
	//計算刪除后的子樹的高度變化
	if((newleftchild==NULL)&&(right()==NULL))
		flag=1;
	//計算刪除后的子樹對當前的根結點的平衡因子的影響
	if (newleftchild==NULL)
		bf++;
	else if((newleftchild->bf!=oldbf)&&(newleftchild->bf==0))
		bf++;
	if (bf>1)//失衡
	{//調整
		int newoldbf=right()->bf;
	    if (newoldbf<0)//雙旋轉
		{
	       return RL_doubleRotation();
		}
	    else
		{//單旋轉
		   return RR_singleRotation();
		}
	}
	return this;
}


template <class T> avlNode<T>* avlNode<T>::findNodeValue(T val)
{
	if (val==value)
	{
		return this;
	}
	else if (val>value)
	{//大于的話在右子樹中查找
		if (right()!=NULL)
			return right()->findNodeValue(val);//遞歸調用
		else 
			return NULL;
	}
	else
	{//小于的話在左子樹中查找
		if (left()!=NULL)			
			return left()->findNodeValue(val);//遞歸調用
		else
			return NULL;
	}
}
template <class T> void avlNode<T>::preorderview(avlNode<T> *current,int i)
{
	i++;//層計數器
	if (current)
	{
		cout<<setw(8)<<current->value<<setw(10)<<current->bf<<" "<<setw(6)<<i<<endl;
		preorderview(current->left(),i);//遞歸調用
		preorderview(current->right(),i);//遞歸調用
	}
}

template <class T> avlNode<T>* avlNode<T>::LL_singleRotation()
{
	avlNode<T> *p;
	p=left();
	left(p->right());
	bf=0;
	p->right(this);
    if(p->bf==0)
	  p->bf=1;
	else p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::LR_doubleRotation()
{
	avlNode<T> *p,*q;
	q=left();
	p=q->right();
	q->right(p->left());
	left(p->right());
	p->left(q);
	bf=q->bf=0;
	if(p->bf==-1) bf=1;
	if(p->bf==1) q->bf=-1;
	p->right(this);
	p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::RR_singleRotation()
{
	avlNode<T> *p;
	p=right();
	right(p->left());
	bf=0;
	p->left(this);
    if(p->bf==0) 
	  p->bf=-1;
	else p->bf=0;
	return p;
}

template <class T> avlNode<T>* avlNode<T>::RL_doubleRotation()
{
	avlNode<T> *p,*q;
	q=right();
	p=q->left();
	q->left(p->right());
	right(p->left());
	p->right(q);
	bf=q->bf=0;
	if(p->bf==-1) q->bf=1;
	if(p->bf==1) bf=-1;
	p->left(this);
	p->bf=0;
	return p;
}