Download Código Fuente 1
Document related concepts
no text concepts found
Transcript
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