#include<iostream>
#include<string>
using namespace std;
template <class Type> class AVLTree
{
friend istream& operator >> (istream&in, AVLTree<Type>& Tree);
friend ostream& operator << (ostream& out, AVLTree<Type>& Tree);
public:
struct AVLNode{
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 LeftBlance(AVLNode*&Tree,int &taller);
void RightBlance(AVLNode*&Tree,int &taller);
int Height(AVLNode*t)const;
public:
AVLTree():root(NULL){}
AVLTree(Type Ref):RefValue(Ref),root(NULL){}
int Insert(Type x){int taller;return Insert(root,x,taller);}
void Traverse(AVLNode *ptr,ostream&out)const;
int Height()const;
};
template <class Type> istream& operator>>(istream&in, AVLTree<Type>& Tree)
{
Type item;
cout<<"Construct AVL Tree:\n";
cout<<"Input Data end with"<<"\n";
cin>>Tree.RefValue;
cout<<"Input Data";
in>>item;
while(item!=Tree.RefValue)
{
Tree.Insert(item);
cout<<"Input Data";
in>>item;
}
return in;
}
//
template <class Type> ostream& operator<<(ostream&out, AVLTree<Type>& Tree)
{
out<<"Inorder of the AVL tree:\n";
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);
cout<<" "<<ptr->data;
Traverse(ptr->right,out);
}
}
//
template <class Type> int AVLTree<Type>::Insert(AVLNode*&tree,Type x,int &taller)
{
int success;
if(tree==NULL)
{
tree=new AVLNode( x);
success=tree!=NULL?1:0;
if(success) taller=1;
}
else if(x<tree->data)
{
success=Insert(tree->left,x,taller);
if(taller)
switch(tree->balance){
case -1:LeftBlance(tree,taller);break;
case 0:tree->balance=-1;break;
case 1:tree->balance=0;taller=0;break;
}
}
else if(x>tree->data)
{
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:RightBlance(tree,taller);break;
}
}
return success;
}
template <class Type> void AVLTree<Type>::LeftBlance(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<<"L Tree alreday balance\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>::RightBlance(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<<"R Tree alreday balance\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> void AVLTree<Type>::RotateLeft(AVLNode*Tree,AVLNode*&NewTree)
{
NewTree=Tree->right;
Tree->right=NewTree->left;
NewTree->left=Tree;
}
template <class Type> void AVLTree<Type>::RotateRight(AVLNode*Tree,AVLNode*&NewTree)
{
NewTree=Tree->left;
Tree->left=NewTree->right;
NewTree->right=Tree;
}
main()
{
AVLTree<string> a;
cin>>a;
cout<<a;
}
