#include <iostream>
#include <math.h>>
#include <fstream>

using namespace std;


template <class G>
				class Nodo{
					private:
						Nodo<G>* left;
						Nodo<G>* right;
						Nodo<G>* parent;
						G *key;
					public:
						Nodo(G k){
							this->key=new G(k);
							left=right=parent=NULL;



						}


						Nodo<G>* getParent(){
							return parent;
						}
						Nodo<G>* getLeft(){
							return left;
						}
						Nodo<G>* getRight(){
							return right;
						}

						G getKey(){
							return *key;
						}


						void setLeft(Nodo<G>* left){
							this->left=left;
						}
						void setRight(Nodo<G>* right){
							this->right=right;
						}

						void setParent(Nodo<G>* parent){
							this->parent=parent;
						}
						void setKey(G item){
							this->key=new G(item);
						}

				};



template <class H>
			class Albero{
				private:
					Nodo<H>* root;

				public:
					Albero(){
						root=NULL;
					}
					Albero<H>* insert(H item){
						Nodo<H>* nuovo=new Nodo<H>(item);
						if(root==NULL){
							root=nuovo;
							return this;
						}


						Nodo<H>* iter=root;
						Nodo<H>* par=NULL;
						while(iter!=NULL){
							par=iter;
							if(iter->getKey()<item){
								iter=iter->getRight();
							}else{
								iter=iter->getLeft();
							}



						}

						if(par==NULL){
							return NULL;
						}
						else{
							if(par->getKey()<item){
								par->setRight(nuovo);
							}else
								par->setLeft(nuovo);
						}

						nuovo->setParent(par);
						return this;
					}








					void inorder(){
						_inorder(root);
					}

					void _inorder(Nodo<H>* start){
						if(start!=NULL){
							_inorder(start->getLeft());
							cout<<start->getKey()<<" ";
							_inorder(start->getRight());
						}

					}





					void ricerca(H item){
						_ricerca(root,item);
					}


					Nodo<H>* _ricerca(Nodo<H>* start,H item){
						while(start!=NULL && start->getKey()!=item){
							if(start->getKey()<item){
								start=start->getRight();
							}else{
								start=start->getLeft();
							}


						}
							if(start==NULL){

								return NULL;
							}else{
						//		cout<<start->getKey();
								return start;
							}


					}


					void mini(){
						return _mini(root);

					}

					Nodo<H>* _mini(Nodo<H>* start){
						if(start->getLeft()!=NULL){

							start=start->getLeft();
						}

						return start;


					}


					H* successore(H item){
						Nodo<H>* ric=_ricerca(root,item);
						if(ric==NULL){
							return NULL;
						}
						Nodo<H>* succ=_successore(ric);
						if(succ==NULL){
							return NULL;
						}
						cout<<succ->getKey();
						return new H(succ->getKey());
					}

					Nodo<H>* _successore(Nodo<H>* start){
							if(start->getRight()!=NULL){
								return _mini(start->getRight());
							}

							Nodo<H>* par=start->getParent();

							while(par!=NULL && par->getKey()<start->getKey()){

								par=par->getParent();
							}



							return par;





					}




					void cancella(H item){
						_cancella(root,item);
					}



					void _cancella(Nodo<H>* start,H item){
	Nodo<H>* ric=_ricerca(start,item);

	if(ric==NULL){
		return;
	}

	Nodo<H>* par=ric->getParent();


	if(!ric->getLeft() || !ric->getRight()){
		Nodo<H>* under=ric->getRight();
		if(ric->getLeft()){
			under=ric->getLeft();
		}

		if(par==NULL){
			root=under;
		}
		else{
			if(par->getLeft()==ric){
				par->setLeft(under);
			}else{
				par->setRight(under);
			}

		}

		if(under!=NULL){
			under->setParent(par);
		}



	}else{
		Nodo<H>* succ=_successore(ric);
		ric->setKey(succ->getKey());
		_cancella(ric->getRight(),succ->getKey());

	}

	return;

}



					int bilanciamento(H item){
						return _bilanciamento(root,item);
					}

					int _bilanciamento(Nodo<H>* start, H item){
						Nodo<H>* ric=_ricerca(start,item);
						int i=0;
						Nodo<H>* sinistra=ric;
						while(sinistra->getLeft()!=NULL){

							sinistra=sinistra->getLeft();

							i++;
						}
						int j=0;
						while(ric->getRight()!=NULL){
							ric=ric->getRight();
							j++;
						}
						cout<<i<<j;

						i=abs(i-j);
						cout<<"   "<<i;
					}



					void peso(H item){
						Nodo<H>* ric=_ricerca(root,item);
						int sx=0;
						int dx=0;
					//	int bal=ric->getKey();
						int lb=_peso(ric->getLeft(),sx);
						int rb=_peso(ric->getRight(),dx);
						cout<<abs(lb-rb);
						// bal += abs(lb + rb);
						//cout<<bal;
					}


					int _peso(Nodo<H>* start,int &num){
						if(start!=NULL){
							num++;
							_peso(start->getLeft(),num);
							_peso(start->getRight(),num);
						}

						return num;




					}
					void leaf(){
						int c=0;
						c= _leaf(c,root);
						cout<<c;
					}


					int _leaf(int &c,Nodo<H>* start){

						if(start->getRight()==NULL && start->getLeft()==NULL){
							c++;



						}



						if(start->getRight()!=NULL){
							_leaf(c,start->getRight());
						}
						if(start->getLeft()!=NULL){
							_leaf(c,start->getLeft());
						}

						return c;
					}


			};




int main(){

	Albero<int>* bst=new Albero<int>();

	bst->insert(3);
	bst->insert(48);
	bst->insert(158);
	bst->insert(6);
	bst->insert(224);
	bst->insert(273);
	bst->insert(297);
	bst->insert(150);
	bst->insert(280);
	bst->insert(200);
//	bst->cancella(127);
	bst->inorder();
//	bst->predecessore(230);
//	bst->successore(223);
//	bst->ricerca(4);
	bst->bilanciamento(158);
//	bst->peso(158);
//	bst->leaf();
}