#include "iostream.h"

	template <class Type> class AVLTree 
	{					//平衡的二叉搜索樹（AVL）類定義

	public:
	   struct AVLNode {							//AVL樹結點的類定義  
		 Type data;  AVLNode *left, *right;  int balance;
		 AVLNode ( ) : left (NULL), right (NULL), balance (0) { }
		 AVLNode ( Type d, AVLNode *l=NULL, AVLNode *r=NULL ) :
	           data (d), left (l), right (r), balance (0) { }
	   };
	
	protected:
	   Type RefValue;										//插入結束的標志
	   AVLNode *root;										//根結點的指針
	   int Insert ( AVLNode* &tree, Type x, int & taller );				//插入
	   void RotateLeft ( AVLNode *Tree, AVLNode* &NewTree );			//左單旋轉
	   void RotateRight ( AVLNode *Tree, AVLNode* &NewTree );			//右單旋轉
	   void LeftBalance ( AVLNode* &Tree, int & taller );				//左平衡化
	   void RightBalance ( AVLNode* &Tree, int & taller );				//右平衡化
	   int Depth ( AVLNode *t ) const;							//求高度
	   void Traverse ( AVLNode *ptr, ostream & out )const ;
	public:
	   AVLTree ( ) : root (NULL) { }								//構造函數：構造一棵空AVL樹
	   AVLTree ( Type Ref ) : RefValue (Ref), root (NULL) { }				//構造函數：構造非空AVL樹
	   int Insert ( Type x ) { int taller; return Insert ( root, x, taller ); }
	   friend istream& operator >> ( istream& in, AVLTree<Type>& Tree );
	   friend ostream& operator << ( ostream& out, const AVLTree<Type>& Tree );
	   int Depth ( ) const;
	};

		template <class Type> void AVLTree<Type>::RotateLeft ( AVLNode * Tree, AVLNode* &NewTree )
		{
		//右子樹比左子樹高: 對以Tree為根的AVL樹做左單旋轉(左折), 旋轉后新根在NewTree。
		   NewTree = Tree->right;					//新的根為C
		   Tree->right = NewTree->left;				//結點C的左子女轉為結點A的右子女
		   NewTree->left = Tree;					//結點A成為C的左子女
		};
		template <class Type> void AVLTree<Type>::RotateRight ( AVLNode *Tree, AVLNode* &NewTree )
		{
		//左子樹比右子樹高: 對以Tree為根的AVL樹做右單旋轉(右折), 旋轉后新根在NewTree。
		   NewTree = Tree->left;					//新的根在B
		   Tree->left = NewTree->right;				//結點B的右子女轉為A的左子女
		   NewTree->right = Tree;					//結點A成為B的右子女
		};

	 
		template <class Type> void AVLTree<Type>::LeftBalance ( AVLNode * &Tree, int & taller ) {
		   AVLNode *leftsub = Tree->left,  *rightsub;
		   switch ( leftsub->balance ) {							//判斷左子樹的平衡因子
			 case -1 :	Tree->balance = leftsub->balance = 0;		//左高，修改平衡因子
					RotateRight ( Tree, Tree );	taller = 0;  break;	//做右單旋轉
			 case 0 :	cout << "LeftBalance error: Tree already balanded.\n";  
				        break;	//沒有發生不平衡
			 case 1 :	rightsub = leftsub->right;					//右高, 取左子樹的右子樹
					switch ( rightsub->balance ) {				//判斷該右子樹的平衡因子
					   case -1: Tree->balance = 1;  
								leftsub->balance = 0;  break;
					   case 0 : Tree->balance = leftsub->balance = 0;  
								break;
					   case 1 : Tree->balance = 0;  
						        leftsub->balance = -1;  
								break;
					}								//調整旋轉后各結點的平衡因子
					rightsub->balance = 0;	
					RotateLeft ( leftsub, Tree->left );				//左單旋轉
					RotateRight ( Tree, Tree );	taller = 0;			//右單旋轉
				}
	}

		template <class Type> void AVLTree<Type>::RightBalance ( AVLNode * &Tree, int & taller ) {
		   AVLNode *rightsub = Tree->right,  *leftsub;
		   switch ( rightsub->balance ) {						//判斷右子樹的平衡因子
			 case 1 :	Tree->balance = rightsub->balance = 0;		//右高
					RotateLeft ( Tree, Tree );  
					taller = 0;  break;		//做左單旋轉
			 case 0 :	cout << "RightBalance error:Tree already balanded.\n";  
				        break;
			 case -1 :	leftsub = rightsub->left;					//左高, 取右子樹的左子樹
					switch ( leftsub->balance ) {				//判斷該左子樹的平衡因子
					   case 1 : Tree->balance = -1; 
						        rightsub->balance = 0;  
								break;
					   case 0 : Tree->balance = rightsub->balance = 0;  
						        break;
					   case -1 : Tree->balance = 0;  
						         rightsub->balance = 1;  
								 break;
					}
					leftsub->balance = 0;
					RotateRight ( rightsub, Tree->right );			//右單旋轉
					RotateLeft ( Tree, Tree );  taller = 0;			//左單旋轉
	   }
	}

		template <class Type> int AVLTree<Type>::Insert ( AVLNode* &tree, Type x, int &taller ) {
		//在以tree為根的AVL樹中插入新元素x, 如果插入成功, taller返回1, 否則返回0。 
		   int success;
		   if ( tree == NULL ) {								//原為空樹, 或某結點的空鏈域
			 tree = new AVLNode (x);							//創建新結點并插入
			 success = tree != NULL ? 1 : 0;						//成功標志: 存儲分配成功為1
			 if ( success )
				 taller = 1;
		   }
		   else if ( x < tree->data ) {							//判斷是向左插入還是向右插入
			 success = Insert ( tree->left, x, taller );					//插入到左子樹
			 if ( taller )									//插入成功 
			   switch ( tree->balance ) {						//判斷平衡因子
				 case -1 :	LeftBalance ( tree, taller );  
					        break;		//原左子樹高，不平衡，調整
				 case 0 :	tree->balance = -1;  
					        break;			//原兩子樹等高，僅改平衡因子
				 case 1 :	tree->balance = 0;  
					        taller = 0;  
					        break;	//原右子樹高，僅改平衡因子
			   }      
		   }
	        else {
			   success = Insert ( tree->right, x, taller );				//插入到右子樹
			   if ( taller )								//插入成功
				 switch ( tree->balance ) {					//判斷平衡因子
				 case -1 :	tree->balance = 0;
							taller = 0;  
							break;	//原左子樹高， 僅改平衡因子
				 case 0 :	tree->balance = 1;  
							break;			//原兩子樹等高， 僅改平衡因子
				 case 1 :	
					        RightBalance ( tree, taller );  
							break;		//原右子樹高，不平衡，調整
			   }
				}
		return success;									//向上層傳送插入成功信息
		}

		template <class Type> istream & operator >> ( istream & in, AVLTree<Type> & Tree ) {
		//輸入一系列的值, 建立AVL樹。約定Tree中的RefValue是終止輸入的標記。
		   Type item;									//輸入暫存單元
		   cout << "Construct AVL tree :\n";						//提示：構造AVL樹
		   cout << "Input Data (end with " << Tree.RefValue << "): ";		//提示：輸入數據(以RefValue結束
		   in >> item;									//輸入
		   while ( item != Tree.RefValue ) {						//當輸入不等于RefValue時
		      Tree.Insert (item);								//插入到樹中			 
		      cout << "Input Data (end with " << Tree.RefValue << "): ";		//提示：輸入數據(以RefValue結束
		      in >> item;									//輸入
		   }
		   return in;
		}

		template <class Type> ostream & operator << ( ostream & out, const AVLTree<Type> & Tree ) {
		   out << "Inorder traversal of AVL tree.\n";					//提示：AVL樹的中序遍歷
		   Tree.Traverse ( Tree.root, out );						//以中序次序輸出樹中各結點的數據
		   out << endl;
		   return out;									//返回輸出對象
		}

		template <class Type> void AVLTree <Type>::Traverse ( AVLNode *ptr, ostream & out ) const {
		   if ( ptr != NULL ) {								//樹非空
		      Traverse ( ptr->left, out );						//中序遍歷左子樹
		      out << ptr->data << ' ';							//輸出根的數據
		      Traverse ( ptr->right, out );						//中序遍歷右子樹			  
		   }
		}