Download Código Fuente 1

CAPÍTULO 14
Árboles binarios equilibrados
EJEMPLO 14.2
Rotación derecha-izquierda
Como se observa en la figura 14.6 al insertar el nodo con clave 6 en el arbol mostrado, se sigue el camino derecha de 4 e
izquierda de 7 para terminar insertando por la derecha de 5. Al regresar por el camino de búsqueda los factores de
equilibrio se incrementan en 1 si se fue por la rama derecha y se decrementan en uno cuando se fue por la rama
izquierda. En el nodo 4 el equilibrio se rompe, por lo que será necesario efectuar una rotación derecha-izquierda con la
finalidad de restablecerlo. El nodo que ahora puede actuar como raiz es el antepenúltimo visitado en el camino de
vuelta, es decir el 5 (figura 14.7)
Figura 14.6. Inserción de un elemento y actualización de los factores de equilibrio
Figura 14.7. Rotación derecha-izquierda
PROBLEMAS RESUELTOS
14.11
#include <stdio.h>
#include <stdlib.h>
1
2
Estructura de datos. Problemas en Pascal
typedef struct Arbol
{
int e;
struct Arbol* izq;
struct Arbol* der;
}arbol;
int vacio(arbol* a);
void recorreras(arbol * a, int n);
void arbolr(int n, arbol** a, FILE* f);
int main()
{
int n;
char pausa;
arbol* a;
FILE * f;
if ((f = fopen ("arminimo.dat", "rt")) == NULL)
{
puts ("Error de apertura para lectura ");
exit(1);
}
//el primer entero es el número de nodos
fscanf (f, "%d", &n);
arbolr(n, &a, f);
fclose(f);
printf("Valores
Nivel\n");
recorreras(a, 1);
pausa = getchar();
return 0;
}
void arbolr(int n, arbol** a, FILE* f)
{
int nizq;
int nder;
if (n == 0)
*a = NULL;
// no existen datos el árbol es vacío
else
{
nizq = n / 2; // nodos que van a la izquierda
nder = n - nizq - 1; // nodos que van a la derecha
*a = (arbol*)malloc(sizeof(arbol));
arbolr(nizq, &(*a)->izq, f);
fscanf(f,"%d ",&(*a)->e);
arbolr(nder, &(*a)->der, f);
}
}
int vacio(arbol* a)
{
return a == NULL;
}
void recorreras(arbol * a, int n)
{
if (! vacio(a))
{
recorreras(a->izq, n+1);
printf(" %d
%d\n", a->e, n);
recorreras(a->der, n+1);
}
}
14.12.
#include <stdio.h>
#include <stdlib.h>
Árboles equilibrados
#define True 1
#define False 0
typedef struct Arbol
{
int info;
struct Arbol* izq;
struct Arbol* der;
int Fe;
}arbol;
void inicializar(arbol ** a);
int vacio(arbol* a);
void insertar(arbol ** a, int e, int* sw);
void borrar(arbol ** a, int c, int* sw);
void buscar(arbol * a, int c, int* encontrado);
void recorreras(arbol * a);
void recorrerdes(arbol * a);
arbol* construir(arbol * a, int e, arbol* b);
void menor(arbol* a, int * e);
void eliminar( arbol ** a, int * sw);
void rotacioniisimple(arbol** a);
void rotacionddsimple(arbol** a);
void rotacioniddoble(arbol** a);
void rotaciondidoble(arbol** a);
void actualizarizq(arbol** a, int* sw);
void actualizarder(arbol** a, int* sw);
void rotacionii2(arbol** a);
void rotaciondd2(arbol** a);
void actualizarbd(arbol** a, int* sw);
void actualizarbi(arbol** a, int * sw);
void dibujar(arbol* a, int h);
//Programa principal
int main()
{
int nm;
char pausa;
arbol* a;
int sw;
inicializar (&a);
printf("Deme numero (0 -> Fin): ");
scanf("%d*c ", &nm);
while (nm !=0)
{
insertar(&a,nm,&sw);
dibujar (a, 0);
puts("");
printf("Deme numero (0 -> Fin): ");
scanf("%d*c ", &nm);
}
printf("Deme numero a borrar(0 -> Fin): ");
scanf("%d*c ", &nm);
while (nm !=0)
{
borrar(&a,nm,&sw);
dibujar (a, 0);
puts("");
printf("Deme numero a borrar(0 -> Fin): ");
scanf("%d%*c ", &nm);
}
pausa = getchar();
return 0;
}
void inicializar(arbol ** a)
{
*a = NULL;
}
int vacio(arbol* a)
{
3
4
Estructura de datos. Problemas en Pascal
return a == NULL;
}
void buscar(arbol * a, int c, int * encontrado)
{
if (vacio(a))
*encontrado = False;
else
if (a->info == c)
*encontrado = True;
else
if (a->info > c)
buscar(a->izq, c, encontrado);
else
buscar(a->der, c, encontrado);
}
/* El procedimiento empleado es análogo al de inserción en un árbol binario,
pero regresar por el camino de búsqueda si sw está activo se calcula el
nuevo factor de equilibrio de los nodos
*/
void insertar(arbol ** a, int e, int * sw)
{
if (vacio(*a))
{
*a = construir(NULL, e, NULL);
(*a)->Fe = 0;
*sw =True;
}
else
if ((*a)->info > e)
{
insertar(& (*a)->izq, e, sw);
if (*sw)
actualizarizq(a, sw);
}
else
if ((*a)->info < e)
{
insertar(& (*a)->der, e, sw);
if (*sw)
actualizarder(a, sw);
}
else
*sw = False;
}
arbol* construir(arbol * a, int e, arbol * b)
{
arbol* nuevo;
nuevo = (arbol*)malloc(sizeof(arbol));
nuevo->info = e;
nuevo->izq = a;
nuevo->der = b;
return nuevo;
}
/* Los casos a considerar son:
La rama derecha era más alta que la izquierda, así que un nuevo elemento en la rama
izquierda consigue que las dos adquieran la misma altura. El subarbol ha dejado de crecer
y sw se desactiva.
Las ramas izquierda y derecha del nodo considerado tenían anteriormente la misma
altura por lo que, al insertar un elemento en la rama izquierda, su altura se hará mayor
que la de la derecha
La rama izquierda era más alta que la derecha y un nuevo elemento en la rama izquierda
rompe el equilibrio del arbol y hace que sea necesaria su reestructuración.
*/
void actualizarizq(arbol** a, int* sw)
{
Árboles equilibrados
5
switch ((*a)->Fe)
{
case 1:
(*a)->Fe = 0;
*sw = False;
break;
case 0:
(*a)->Fe = -1;
break;
case -1:
if ((*a)->izq->Fe == -1)
rotacioniisimple(a);
else
rotacioniddoble(a);
*sw = False;
break;
}
}
/* Los casos a considerar son:
La rama izquierda era más alta que la derecha, así que un nuevo elemento en la rama
derecha consigue que las dos adquieran la misma altura. El subarbol ha dejado de crecer y
sw se desactiva.
Las ramas izquierda y derecha del nodo considerado tenían anteriormente la misma
altura por lo que, al insertar un elemento en la rama derecha, su altura se hará mayor
que la de la izquierda
La rama derecha era más alta que la izquierda y un nuevo elemento en la rama derecha
rompe el equilibrio del arbol y hace que sea necesaria su reestructuración.
*/
void actualizarder(arbol** a, int* sw)
{
switch ((*a)->Fe)
{
case -1:
(*a)->Fe = 0;
*sw = False;
break;
case 0:
(*a)->Fe = 1;
break;
case 1:
if ((*a)->der->Fe == 1)
rotacionddsimple(a);
else
rotaciondidoble(a);
*sw = False;
break;
}
}
/* El hijo izquierdo del nodo actual ocupara en el árbol el lugar
del nodo actual. Hay que actualizar los factores de equilibrio.
*/
void rotacioniisimple(arbol** a)
{
arbol* p;
p = (*a)->izq;
(*a)->izq = p->der;
p->der = *a;
p->Fe = 0;
(*a)->Fe = 0;
*a = p;
}
/* El hijo derecho del nodo actual ocupara en el árbol el lugar
del nodo actual. Hay que actualizar los factores de equilibrio.
*/
void rotacionddsimple(arbol** a)
{
6
Estructura de datos. Problemas en Pascal
arbol* p;
p = (*a)->der;
(*a)->der = p->izq;
p->izq = *a;
p->Fe = 0;
(*a)->Fe = 0;
*a = p;
}
/* El hijo derecho del hijo izquierdo del nodo actual es el que se colocará
en la posición del nodo actual. Hay que actualizar los factores de equilibrio.
*/
void rotacioniddoble(arbol** a)
{
arbol* p1;
arbol* p2;
p1 = (*a)->izq;
p2 = p1->der;
p1->der = p2->izq;
p2->izq = p1;
(*a)->izq = p2->der;
p2->der = *a;
if (p2->Fe == 1)
p1->Fe = - 1;
else
p1->Fe = 0;
if (p2->Fe == -1)
(*a)->Fe = 1;
else
(*a)->Fe = 0;
p2->Fe = 0;
*a = p2;
}
/* El hijo izquierdo del hijo derecho del nodo actual es el que se colocará
en la posición del nodo actual. Hay que actualizar los factores de equilibrio.
*/
void rotaciondidoble(arbol** a)
{
arbol* p1;
arbol* p2;
p1 = (*a)->der;
p2 = p1->izq;
p1->izq = p2->der;
p2->der = p1;
(*a)->der = p2->izq;
p2->izq = *a;
if (p2->Fe == 1)
(*a)->Fe = -1;
else
(*a)->Fe = 0;
if (p2->Fe == -1)
p1->Fe = 1;
else
p1->Fe = 0;
p2->Fe = 0;
*a = p2;
}
/* El procedimiento empleado es análogo al de borrado en un árbol binario,
pero regresar por el camino de búsqueda si sw está activo se calcula el
nuevo factor de equilibrio de los nodos
*/
void borrar(arbol ** a, int c, int * sw)
{
if (*a != NULL )
if ((*a)->info == c)
eliminar(a, sw);
else
if ((*a)->info > c)
{
borrar(&(*a)->izq, c, sw);
Árboles equilibrados
if (*sw)
actualizarbi(&(*a), sw);
}
else
{
borrar(&(*a)->der, c, sw);
if (*sw)
actualizarbd(&(*a), sw);
}
}
void menor(arbol* a, int* e)
{
if (a->izq == NULL)
*e = a->info;
else
menor(a->izq, e);
}
void eliminar( arbol ** a, int * sw)
{
arbol* auxi;
int e;
if ((*a)->izq == NULL)
{
auxi = *a; *a = (*a)->der;
free (auxi);
*sw = True;
}
else
if ((*a)->der == NULL)
{
auxi = *a; *a = (*a)->izq;
free (auxi);
*sw = True;
}
else
{
menor((*a)->der, & e); (*a)->info = e;
borrar(&(*a)->der, e, sw);
if (*sw)
actualizarbd(a, sw);
}
}
/*
El factor de equilibrio del nodo actual aumenta en una unidad pues el borrado
se ha efectuado por la izquierda. Si el anterior factor de equilibrio del
nodo actual era 1 es necesario reestructurar y considerar tres tipos
de rotaciones.
*/
void actualizarbi(arbol** a, int * sw)
{
switch ((*a)->Fe)
{
case -1:
(*a)->Fe = 0;
break;
case 0:
(*a)->Fe = 1;
*sw = False;
break;
case 1:
switch ((*a)->der->Fe)
{
case 1:
rotacionddsimple(a);
break;
case -1:
rotaciondidoble(a);
break;
case 0:
rotaciondd2(a);
7
8
Estructura de datos. Problemas en Pascal
*sw = False;
break;
}
}
}
/* El factor de equilibrio del nodo actual disminuye en una unidad pues
el borrado se ha efectuado por la derecha. Si el anterior factor
de equilibrio era -1 es necesario reestructurar y considerar los tres
tipos de rotaciones posibles.
*/
void actualizarbd(arbol** a, int* sw)
{
switch ((*a)->Fe)
{
case 1:
(*a)->Fe = 0;
break;
case 0:
(*a)->Fe = -1;
*sw = False;
break;
case -1:
switch ((*a)->izq->Fe)
{
case -1:
rotacioniisimple(a);
break;
case 1:
rotacioniddoble(a);
break;
case 0:
rotacionii2(a);
*sw = False;
break;
}
}
}
/* rotación específica del borrado, que se diferencia de la rotacioniisimple
en los factores de equilibrio adjudicados a los nodos implicados
*/
void rotacionii2(arbol** a)
{
arbol* p;
p = (*a)->izq;
(*a)->izq = p->der;
p->der = *a;
p->Fe = 1;
(*a)->Fe = -1;
*a = p;
}
/* rotación específica del borrado que se diferencia de la rotacionddsimple
en los factores de equilibrio adjudicados a los nodos implicados
*/
void rotaciondd2(arbol** a)
{
arbol* p;
p = (*a)->der;
(*a)->der = p->izq;
p->izq = *a;
p->Fe = -1;
(*a)->Fe = 1;
*a = p;
}
void dibujar(arbol* a, int nivel)
{
int i;
if (a != NULL)
{
Árboles equilibrados
dibujar(a -> der, nivel+1);
for (i = 1; i <= nivel; i++) printf("
printf("%d\n",a -> info);
dibujar(a -> izq, nivel+1);
}
}
void recorreras(arbol * a)
{
if (! vacio(a))
{
recorreras(a->izq);
printf(" %d ", a->info);
recorreras(a->der);
}
}
void recorrerdes(arbol * a)
{
if (! vacio(a))
{
recorrerdes(a->der);
printf(" %d ", a->info);
recorrerdes(a->izq);
}
}
");
9