using namespace std;

struct NODO
{
   NODO *izq;
	int       info;
	NODO *der;
	int		 FE;
};

void InsercionBalanceado(NODO **nodocabeza, bool *BO, int infor);
void Busqueda(NODO *nodo,int infor);
void Preorden(NODO *);
void Inorden(NODO *);
void Postorden(NODO *);
void Restructura1(NODO **nodocabeza, bool *BO);
void Restructura2(NODO **nodocabeza, bool *BO);
void Borra(NODO **aux1, NODO **otro1, bool *BO);
void EliminacionBalanceado(NODO **nodocabeza, bool *BO, int infor);
int Menu();

int main()
{
   int Opcion;
   int elemento;
   NODO *borrado, *raiz;
   raiz=NULL;
   system("cls");
   Opcion = Menu();
   bool inicio;
   while (Opcion)
   {
      system("cls");
		switch(Opcion)
      {
         case 1:
            cout<<"\nRUTINA DE INSERCION\n\n";
            cout<<"\nIngrese elemento a insertar: ";
            cin>>elemento;
            inicio=false;
            InsercionBalanceado(&raiz, &inicio, elemento);
            break;

         case 2:
				cout<<"\nRUTINA DE BUSQUEDA\n\n";
            cout<<"\nIngrese elemento a buscar: ";
            cin>>elemento;
            Busqueda(raiz, elemento);
            break;
         case 3:
            printf("\nRECORRIDO PREORDEN\n\n");
            printf("\nEl arbol es: \n\n");
         	Preorden(raiz);
            printf("\n\n");
            system("pause");
            break;
         case 4:
            printf("\nRECORRIDO INORDEN\n\n");
            printf("\nEl arbol es: \n\n");
				Inorden(raiz);
				printf("\n\n");
            system("pause");
            break;
         case 5:
            printf("\nRECORRIDO POSTORDEN\n\n");
            printf("\nEl arbol es: \n\n");
            Postorden(raiz);
            printf("\n\n");
            system("pause");
            break;
      	case 6:
				cout<<"\nRUTINA DE ELIMINACION\n\n";
            cout<<"\nIngrese elemento a eliminar: ";
            cin>>elemento;
            inicio=false;
            EliminacionBalanceado(&raiz, &inicio, elemento);
            break;
         case  0: exit(0);
      }
      Opcion = Menu();
   }
   system("pause");
   return(0);
}
int Menu()
{
   int Op;
   do{
      system("cls");
      cout<<"\n\n\t    ARBOL  BINARIO BALANCEADO \n\n";
      cout<<"\t1) Insertar\n";
		cout<<"\t2) Buscar\n";
		cout<<"\t3) PreOrden\n";
		cout<<"\t4) InOrden\n";
		cout<<"\t5) PostOrden\n";
		cout<<"\t6) Eliminacion\n";
		cout<<"\t0) Salir\n\n";
      printf("Digite su opcion ---> ");
      cin>>Op;
   }while(Op<0 || Op>7);
   return (Op);
}

void InsercionBalanceado(NODO **nodocabeza, bool *BO, int infor)
{
	NODO *nodo, *nodo1, *nodo2; 
   nodo=*nodocabeza;
   if(nodo!=NULL)
	{
		if( infor < nodo->info )
		{
			InsercionBalanceado(&(nodo->izq),BO,infor);
			if( *BO == true )
			{
				switch(nodo->FE)
				{
					case 1:	nodo->FE=0;
								*BO=false;
								break;
					case 0:	nodo->FE=-1;
								break;
					case -1:	nodo1=nodo->izq;//reestructuracion del arbol
								if (nodo1->FE<=0)
								{	//Rotacion II
									nodo->izq=nodo1->der;
									nodo1->der=nodo;
									nodo->FE=0;
									nodo=nodo1;
								}
								else
								{	//Rotacion ID
									nodo2=nodo1->der;
									nodo->izq=nodo2->der;
									nodo2->der=nodo;
									nodo1->der=nodo2->izq;
									nodo2->izq=nodo1;
																
									if (nodo2->FE==-1)
										nodo->FE=1;
									else
										nodo->FE=0;
								
									if (nodo2->FE==1)
										nodo1->FE=-1;
									else
										nodo1->FE=0;
									nodo=nodo2;
								}
								nodo->FE=0;
								*BO=false;								
								break;
				}
			}	
		}
		else
		{
			if( infor > nodo->info )
			{
				InsercionBalanceado(&(nodo->der),BO,infor);
				if( *BO == true )
				{
					switch(nodo->FE)
					{
						case -1:	nodo->FE=0;
									*BO=false;
									break;
						case 0:	nodo->FE=1;
									break;
						case 1:	nodo1=nodo->der;//reestructuracion del arbol
									if (nodo1->FE>=0)
									{	//Rotacion DD
										nodo->der=nodo1->izq;
										nodo1->izq=nodo;
										nodo->FE=0;
										nodo=nodo1;
									}
									else
									{	//Rotacion DI
										nodo2=nodo1->izq;
										nodo->der=nodo2->izq;
										nodo2->izq=nodo;
										nodo1->izq=nodo2->der;
										nodo2->der=nodo1;
															
										if (nodo2->FE==1)
											nodo->FE=-1;
										else
											nodo->FE=0;
							
										if (nodo2->FE==-1)
											nodo1->FE=1;
										else
											nodo1->FE=0;
			
										nodo=nodo2;
									}
									nodo->FE=0;
									*BO=false;								
									break;
					}
				}
			}
			else
			{
				cout<<"\nEl nodo ya se encuentra en el arbol\n"<<endl;
				system("pause");
			}				
		}
	}
	else
	{
		//NODO *otro;
      nodo = new(NODO);
      nodo->izq=NULL;
      nodo->der=NULL;
      nodo->info=infor;
      nodo->FE=0;
      *BO=true;
	}
   *nodocabeza=nodo;
}

void Busqueda(NODO *nodo,int infor)
{
	if(nodo!=NULL)
	{
		if( infor < nodo->info )
		{
			Busqueda(nodo->izq,infor);
		}
		else
		{
			if( infor > nodo->info )
			{
				Busqueda(nodo->der,infor);
			}
			else
			{
				cout<<"\nEl nodo SI se encuentra en el arbol\n"<<endl;
				system("pause");
			}
		}
	}
	else
	{
		cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
		system("pause");
	}
}

void Preorden(NODO *nodo)
{
	if (nodo!=NULL)
	{
		cout<<nodo->info<<"\t";
		Preorden(nodo->izq);
		Preorden(nodo->der);
	}
}

void Inorden(NODO *nodo)
{
	if (nodo!=NULL)
	{
		Inorden(nodo->izq);
		cout<<nodo->info<<"\t";
		Inorden(nodo->der);
	}
}

void Postorden(NODO *nodo)
{
	if (nodo!=NULL)
	{
		Postorden(nodo->izq);
		Postorden(nodo->der);
		cout<<nodo->info<<"\t";
	}
}

/*void Eliminacion(NODO **nodocabeza, int infor)
{
	NODO *nodo, *otro, *aux, *aux1; 
   nodo=*nodocabeza;
   if(nodo!=NULL)
	{
		if( infor < nodo->info )
		{
			Eliminacion(&(nodo->izq),infor);
		}
		else
		{
			if( infor > nodo->info )
			{
				Eliminacion(&(nodo->der),infor);
			}
			else
			{
				otro=nodo;
				if (otro->der==NULL)
				{
					nodo=otro->izq;
				}
				else
				{
					if (otro->izq==NULL)
					{
						nodo=otro->der;
					}
					else
					{
						aux=otro->izq;
						aux1=aux;
						while(aux->der!=NULL)
						{
							aux1=aux;
							aux=aux->der;
						}
						otro->info=aux->info;
						otro=aux;
						aux1->der=aux->izq;
					}
				}
			}
		}
		delete(otro);
	}
	else
	{
		cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
		system("pause");
	}
	*nodocabeza=nodo;
}		
*/
void Restructura1(NODO **nodocabeza, bool *BO)
{
	NODO *nodo, *nodo1, *nodo2; 
   nodo=*nodocabeza;
   if ( *BO==true )
   {
		switch(nodo->FE){
			case -1:	nodo->FE=0;
						break;
			case 0:	nodo->FE=1;
						*BO=false;
						break;
			case 1:	//reestructuracion del arbol
						nodo1=nodo->der;
						if(nodo1->FE>=0){	//rotacion DD
							nodo->der=nodo1->izq;
							nodo1->izq=nodo;
							switch (nodo1->FE){
								case 0:	nodo->FE=1;
											nodo1->FE=-1;
											*BO=false;
											break;
								case 1:	nodo->FE=0;
											nodo1->FE=0;
											*BO=false;
											break;											
							}
							nodo=nodo1;
						}
						else
						{	//Rotacion DI
							nodo2=nodo1->izq;
							nodo->der=nodo2->izq;
							nodo2->izq=nodo;
							nodo1->izq=nodo2->der;
							nodo2->der=nodo1;
							
							if (nodo2->FE==1)
								nodo->FE=-1;
							else
								nodo->FE=0;
								
							if (nodo2->FE==-1)
								nodo1->FE=1;
							else
								nodo1->FE=0;
							
							nodo=nodo2;
							nodo2->FE=0;							
						}						
						break;			
		}
	}
   *nodocabeza=nodo;
}

void Restructura2(NODO **nodocabeza, bool *BO)
{
	NODO *nodo, *nodo1, *nodo2; 
   nodo=*nodocabeza;
   if ( *BO==true )
   {
		switch(nodo->FE)
		{
			case 1:	nodo->FE=0;
						break;
			case 0:	nodo->FE=-1;
						*BO=false;
						break;
			case -1:	//reestructuracion del arbol
						nodo1=nodo->izq;
						if(nodo1->FE<=0)
						{	//rotacion II
							nodo->izq=nodo1->der;
							nodo1->der=nodo;
							switch (nodo1->FE)
							{
								case 0:	nodo->FE=-1;
											nodo1->FE=1;
											*BO=false;
											break;
								case -1:	nodo->FE=0;
											nodo1->FE=0;
											*BO=false;
											break;											
							}
							nodo=nodo1;
						}
						else
						{	//Rotacion ID
							nodo2=nodo1->der;
							nodo->izq=nodo2->der;
							nodo2->der=nodo;
							nodo1->der=nodo2->izq;
							nodo2->izq=nodo1;
							
							if (nodo2->FE==-1)
								nodo->FE=1;
							else
								nodo->FE=0;
								
							if (nodo2->FE==1)
								nodo1->FE=-1;
							else
								nodo1->FE=0;
							
							nodo=nodo2;
							nodo2->FE=0;							
						}						
						break;			
		}
	}
   *nodocabeza=nodo;
}

void Borra(NODO **aux1, NODO **otro1, bool *BO)
{
	NODO *nodo, *aux, *otro; 
   aux=*aux1;
   otro=*otro1;
   if ( aux->der!=NULL )
	{
		Borra(&(aux->der),&otro,BO);	
		Restructura2(&aux,BO);
	}
	else
	{
		otro->info=aux->info;
		aux=aux->izq;
		*BO=true;
	}
	*aux1=aux;
	*otro1=otro;
}

void EliminacionBalanceado(NODO **nodocabeza, bool *BO, int infor)
{
	NODO *nodo, *otro; 
   nodo=*nodocabeza;
   if(nodo!=NULL)
	{
		if( infor < nodo->info )
		{
			EliminacionBalanceado(&(nodo->izq),BO,infor);
			Restructura1(&nodo,BO);
		}
		else
		{
			if( infor > nodo->info )
			{
				EliminacionBalanceado(&(nodo->der),BO,infor);
				Restructura2(&nodo,BO);	
			}
			else
			{
				otro=nodo;
				if (otro->der==NULL)
				{
					nodo=otro->izq;
					*BO=true;					
				}	
				else
				{
					if (otro->izq==NULL)
					{
						nodo=otro->der;
						*BO=true;					
					}	
					else
					{
						Borra(&(otro->izq),&otro,BO);
						Restructura1(&nodo,BO);
						delete(otro);
					}
				}
			}
		}	
	}
	else
	{
		cout<<"\nEl nodo NO se encuentra en el arbol\n"<<endl;
		system("pause");
	}
	*nodocabeza=nodo;
}