/*
  Ejercicio # 8
  Nombre: Ejemplo sencillo de Arbol Balanceado
  Autor: Carlos Rolando Calán Ajquill
  Fecha: 07/07/06 01:45
  Descripción: Programa que realiza un balanceado del arbol de acuerdo a los
               datos que ha ingresado el usuario
  Versión: 1.0 
*/

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <conio.h>
using namespace std;
int Numeros[100];
class Nodo
{
  public:
    int clave;
    Nodo *HijoIzq; //Apuntando al hijo izquierdo      
    Nodo *HijoDer; //Apuntando al hijo derecho
    int FB;        //Factor de Balance
  public:
    Nodo(int dato);
};

Nodo::Nodo(int dato) //Constructor
{
  clave = dato;
  HijoIzq = NULL;
  HijoDer = NULL;
  FB = 0;  
}

class ArbolAVL
{
  public:
    Nodo *raiz;
    Nodo *actual;
  public:
    ArbolAVL();    //Constructor
    void insertar(int dato);
    //Recorrido
    void inorden(Nodo *r);
    //Rotaciones
    void Rotacion_a_la_Derecha(Nodo *P, Nodo *Q);
    void Rotacion_a_la_Izquierda(Nodo *P, Nodo *Q);
    Nodo *Doble_Rotacion_a_la_Derecha(Nodo *P, Nodo *Q);
    Nodo *Doble_Rotacion_a_la_Izquierda(Nodo *P, Nodo *Q);
};

//Constructor
ArbolAVL::ArbolAVL()
{
  raiz = NULL;
  actual = NULL;
}

//Rotaciones
void ArbolAVL::Rotacion_a_la_Derecha(Nodo *P, Nodo *Q)
{
  P->HijoIzq = Q->HijoDer;
  Q->HijoDer = P;
  P->FB = 0;
  Q->FB = 0;
}

void ArbolAVL::Rotacion_a_la_Izquierda(Nodo *P, Nodo *Q)
{
  P->HijoDer = Q->HijoIzq;
  Q->HijoIzq = P;
  P->FB = 0;
  Q->FB = 0;
}

Nodo *ArbolAVL::Doble_Rotacion_a_la_Derecha(Nodo *P, Nodo *Q)
{
  Nodo *R = Q->HijoDer;   //Se obtiene R a partir de Q
  int factor_R = R->FB;   //Se guarda el factor de balance R
  Rotacion_a_la_Izquierda(Q,R);
  Rotacion_a_la_Derecha(P,R);
  switch (factor_R)
  {
    case 0:  P->FB = 0;
             Q->FB = 0;       
             break;
    case 1:  P->FB = -1;
             Q->FB = 0;       
             break;
    case -1: P->FB = 0;
             Q->FB = 1;       
             break;
  }
  R->FB = 0; //Aunque sobra ya que las Rotaciones ya lo han puesto en 0
  return R;  //Se devuelve la raiz del arbol balanceado
}

Nodo *ArbolAVL::Doble_Rotacion_a_la_Izquierda(Nodo *P, Nodo *Q)
{
  Nodo *R = Q->HijoIzq;   //Se obtiene R a partir de Q
  int factor_R = R->FB;   //Se guarda el factor de balance R
  Rotacion_a_la_Derecha(Q,R);
  Rotacion_a_la_Izquierda(P,R);
  switch (factor_R)
  {
    case 0:  P->FB = 0;
             Q->FB = 0;       
             break;
    case 1:  P->FB = 0;
             Q->FB = -1;       
             break;
    case -1: P->FB = 1;
             Q->FB = 0;       
             break;
  }
  R->FB = 0; //Aunque sobra ya que las Rotaciones ya lo han puesto en 0
  return R;  //Se devuelve la raiz del arbol balanceado
}

//Algoritmo de Insercion
void ArbolAVL::insertar(int dato)
{
  Nodo *x = new Nodo(dato);  //Crea el nodo para el nuevo
  Nodo *p = raiz;            //Asigna valores iniciales a las variables
  Nodo *q = NULL;            //que se utilizan para buscar el sitio donde
  Nodo *pivote = raiz;       //se insertara el nuevo nodo y determinar
  Nodo *pp = NULL;           //pivote y su padre
  if (raiz == NULL)
  {
    raiz = actual = x;       //El nuevo a su vez es la raiz y el actual
  }
  else
  {
    while (p != NULL)
    {
      if (p->clave == dato)  //Repetido
      {
        delete (x);
        return;
      }
      if (p->FB != 0)        //O sea que es -1 o +1
      {
        pivote = p;          //Determina el pivote
        pp = q;              //Y su padre   
      }
      q = p;                 //Actualiza q
      if (p->clave > dato)
        p = p->HijoIzq;      //Avanza con p
      else
        p = p->HijoDer;      //Avanza con p
    }
    if (q->clave > dato)
      q->HijoIzq = x;        //Inserta x como hijo izquierdo
    else
      q->HijoDer = x;
    //Recalcula factor de balance de pivote
    if (pivote->clave > dato)
    {
      pivote->FB = pivote->FB + 1;
      q = pivote->HijoIzq;
    }
    else
    {
      pivote->FB = pivote->FB - 1;
      q = pivote->HijoDer;
    }
    //Recalcula factores de balance de todos los nodos en la
    //trayectoria desde pivote hata el nodo insertado x
    p = q;
    while (p != x)
    {
      if (p->clave > dato)
      {
        p->FB = 1;
        p = p->HijoIzq;   
      }
      else
      {
        p->FB = -1;
        p = p->HijoDer;   
      }
    }
    if (pivote->FB ==0 || pivote->FB == -1 || pivote->FB == 1)
      //Si el arbol sigui balanceado retorna
      return;
    //Determina el tipo de rotacion
    if (pivote->FB == 2 && q->FB == 1)
      Rotacion_a_la_Derecha(pivote, q);
    if (pivote->FB == -2 && q->FB == -1)
      Rotacion_a_la_Izquierda(pivote, q);  
    if (pivote->FB == 2 && q->FB == -1)
      q = Doble_Rotacion_a_la_Derecha(pivote, q);
    if (pivote->FB == -2 && q->FB == 1)
      q = Doble_Rotacion_a_la_Izquierda(pivote, q);
    //Si el nodo desbalanceado es raiz lo actualiza y regresa
    if (pp == NULL)
    {
      raiz = q;
      return;   
    }
    //Pega la nueva raiz del arbol rebalanceado(q) al nodo pp
    if (pivote == pp->HijoIzq)
      pp->HijoIzq = q;
    else
      pp->HijoDer = q;
  }      
}

void ArbolAVL::inorden(Nodo *r)
{
  if (r)
  {
    inorden(r->HijoIzq);
    cout<<" "<<r->clave<<" ";
    inorden(r->HijoDer);
  }  
}

void MenuCalan()
{
	char Opcion;
	int Datito = 0;
	int Contador = 0;
	ArbolAVL miarbolAVL;
  while (Opcion != 'c' && Opcion != 'C')
  {
    system("CLS");
    cout<<"\t \t \t UNIVERSIDAD MARIANO GALVEZ \n \n"; 
    cout<<"\t \t Proyecto Final Estructura De Datos \n";    
    cout<<"\t \t Carlos Rolando Calan Ajquill    Junio/2006 \n";
    cout<<"\t \t Carne: 0910-04-13429         5to. Semestre \n";
    cout<<"\t \t --------------------------------------------------------\n";    
    cout<<"\t \t                      Arbol Balanceado\n ";
    cout<<"\t \t --------------------------------------------------------\n\n";    
		cout<<"\t A.- Ingreso de Datos \n";
		cout<<"\t B.- Datos Ordenados \n";	
		cout<<"\t C.- Salir \n";
    cout<<"\t -----------------------------------------------------------\n";    
		cout<<"\t \t Seleccione una opcion \t";
		cin>>Opcion;
	  switch (Opcion)
		{
		  case 'a': case 'A':
        cout<<"OPCION A: \n";
        cout<<"Ingrese el Dato \t";
        cin>>Datito;
        Numeros[Contador++] = Datito;
		    miarbolAVL.insertar(Datito);
				break;
			case 'b': case 'B':
        cout<<" OPCION B: \n";
        cout<<" Numeros Ingresados \n";
        for (int i=0; i<Contador; i++)        
        {
          cout<<Numeros[i]<<" ";
        }
        cout<<"\n \n Datos Ordenados \n";
			  miarbolAVL.inorden(miarbolAVL.raiz);
			  getch();
			  break;			
			case 'c': case 'C':        
		    system("CLS");
        cout<<"Hecho por Carlos Rolando Calan Ajquill, hasta pronto ......\n\n";			                
			  break;
      default:
        cout<<"Opcion Invalida \n\n";
        break;	    
 		}
	}
}

int main(int argc, char *argv[])
{
  system("CLS");
  //Se crea un arbol AVL
  ///ArbolAVL miarbolAVL;
  //Se insertan claves en el arbol
  ///miarbolAVL.insertar(9);
  ///miarbolAVL.insertar(6);
  ///miarbolAVL.insertar(1);  //Desencadena rotacion por la derecha
  ///cout<<"\n";
  ///miarbolAVL.inorden(miarbolAVL.raiz);     
  ///cout<<"\n \n";
  MenuCalan();
  system("PAUSE");
  return EXIT_SUCCESS;
}