/*
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;
}