Upload
lkinpark2007
View
142
Download
0
Embed Size (px)
Citation preview
CORPORATIVO INTERNACIONAL UNIVERSITARIO
Nombre: David Peralta Jurez
Profesor: Gabriel Flores Gonzlez
Licenciatura: Informtica Administrativa
Materia: Organizacin de Archivos y estructuras de Datos
Fecha:22 de Enero de 2012
1
INDICEEstructuras lineales3 Algoritmos para manipular listas.12 Algoritmos para manipular Arboles16 Grafos y sus aplicaciones..60 Ordenacin y bsqueda..73
Estructuras lineales2
INTRODUCCIONLas estructuras lineales de datos se caracterizan por que sus elementos estn en secuencia, relacionados en forma lineal, uno de otro. Cada elemento de las estructuras puede estar conformado por uno o barios subelemento o campos que pueden pertenecer a cualquier tipo de datos, pero que normalmente son tipos bsicos.
APLICACIONESLa realizacin de sistemas operativos para los computadores. Los cuales hacen un uso intensivo de las estructuras lineales, ya que internamente se soportan en los sistemas operativos, las colas de ejecucin para los dispositivos, las pilas de llamada a los subprogramas de cualquier programa, las listas de usuarios en los sistemas operativos multiusuario. Las estructuras lineales son importantes porque aparecen con mucha frecuencia en situaciones de la vida Ejemplos: Una cola de clientes de un banco, las instrucciones deun programa, los caracteres de una cadena o las pginas de un libroCaractersticas: existe un nico elemento, llamado primero, existe un nico elemento, llamado ltimo, cada elemento, excepto el primero, tiene un nico predecesory ,cada elemento, excepto el ltimo, tiene un nico sucesor Operaciones: crear la estructura vaca, insertar un elemento, borrar un elemento y obtener un elemento. Para definir claramente el comportamiento de la estructura es necesario determinar en quposicin se insertaun elemento nuevo y quelemento se borrao se obtiene. Principales estructuras lineales: pilas, colas y secuencias.
Pilas
3
Contenedor de objetos que son insertados y eliminados de acuerdo con el principio de que el ltimo en entrar es el primero en salir (LIFO -LastIn FirstOut). Los elementos se insertan de uno en uno (push-apilar)Los elementos se sacan en orden inverso al cual se han insertado (pop-desapilar) El nico elemento que se puede observar es el ltimo insertado (topeo cima).
Especificacin public class Pila { // caractersticas: // Es una secuencia de elementos donde el ltimo en entrar es el primero en ser eliminado // Los objetos son modificables. public Pila ( ) // Produce: una pila vaca public int tamao() // Produce: devuelve el nmero de elementos de la pila public boolean esVacio() // Produce: cierto si la pila est vaca. Falso en otro caso public E top() throws PilaVaciaExcepcion // Produce: si la pila est vaca lanza la excepcin PilaVaciaExcepcion, // sino devuelve el objeto ms recientemente introducido public E pop() throws PilaVaciaExcepcion // Modifica:th // Produce: si la pila est vaca lanza la excepcin PilaVaciaExcepcion, // sino devuelve el objeto ms recientemente introducido y lo suprime de la pila public void push (E elemento) // Modifica: this // Produce: aade un objeto a la pila, pasando a ser el nuevo tope }i s Ejemplo de uso del TAD Pila public class PruebaPila{ public static void main (String []args){ Pila p = new Pila(); for (int i=1; iizq); preorden(a->der); } } * Recorrido en inorden u orden central: se visita el subrbol izquierdo, el nodo actual, y despus se visita el subrbol derecho. En el ejemplo de la figura 1 las visitas seran en este orden: b,d,a,e,c,f. void inorden(tarbol *a) { if (a != NULL) { inorden(a->izq); visitar(a); inorden(a->der); } } * Recorrido en postorden: se visitan primero el subrbol izquierdo, despus el subrbol derecho, y por ltimo el nodo actual. En el ejemplo de la figura 1 el recorrido quedara as: d,b,e,f,c,a. void postorden(arbol *a) {
23
if (a != NULL) { postorden(a->izq); postorden(a->der); visitar(a); } } La ventaja del recorrido en postorden es que permite borrar el rbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrar el rbol o subrbol que se pasa como parmetro. La razn para hacer esto es que no se debe borrar un nodo y despus sus subrboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido. - Recorrido en amplitud: Consiste en ir visitando el rbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raz), despus los nodos de nivel 2, as hasta que ya no queden ms. Si se hace el recorrido en amplitud del rbol de la figura una visitara los nodos en este orden: a,b,c,d,e,f En este caso el recorrido no se realizar de forma recursiva sino iterativa, utilizando una cola (ver Colas) como estructura de datos auxiliar. El procedimiento consiste en encolar (si no estn vacos) los subrboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola est vaca. En la codificacin que viene a continuacin no se implementan las operaciones sobre colas. void amplitud(tarbol *a) { tCola cola; /* las claves de la cola sern de tipo rbol binario */ arbol *aux;
if (a != NULL) { CrearCola(cola);24
encolar(cola, a); while (!colavacia(cola)) { desencolar(cola, aux); visitar(aux); if (aux->izq != NULL) encolar(cola, aux->izq); if (aux->der != NULL) encolar(cola, aux->der); } } } Por ltimo, considrese la sustitucin de la cola por una pila en el recorrido en amplitud. Qu tipo de recorrido se obtiene? Construccin de un rbol binario Hasta el momento se ha visto la declaracin y recorrido de un rbol binario. Sin embargo no se ha estudiado ningn mtodo para crearlos. A continuacin se estudia un mtodo para crear un rbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays. Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el rbol viendo sus recorridos pero sin haber visto el rbol terminado. Partiendo de los recorridos preorden e inorden del rbol de la figura 1 puede determinarse que la raz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raz forman el subrbol izquierdo. Asimismo los elementos entre der y la raz forman el subrbol derecho. Por tanto se tiene este rbol:
25
A continuacin comienza un proceso recursivo. Se procede a crear el subrbol izquierdo, cuyo tamao est limitado por los ndices izq y der. La siguiente posicin en el recorrido en preorden es la raz de este subrbol. Queda esto:
El subrbol b tiene un subrbol derecho, que no tiene ningn descendiente, tal y como indican los ndices izq y der. Se ha obtenido el subrbol izquierdo completo de la raz a, puesto que b no tiene subrbol izquierdo:
Despus seguir construyndose el subrbol derecho a partir de la raz a. La implementacin de la construccin de un rbol partiendo de los recorridos en preorden y en inorden puede consultarse aqu (en C).26
rbol binario de bsqueda Un rbol binario de bsqueda es aquel que es: - Una estructura vaca o - Un elemento o clave de informacin (nodo) ms un nmero finito -a lo sumo dos- de estructuras tipo rbol, disjuntos, llamados subrboles y adems cumplen lo siguiente: * Todas las claves del subrbol izquierdo al nodo son menores que la clave del nodo. * Todas las claves del subrbol derecho al nodo son mayores que la clave del nodo. * Ambos subrboles son rboles binarios de bsqueda. Un ejemplo de rbol binario de bsqueda:
Figura 5 Al definir el tipo de datos que representa la clave de un nodo dentro de un rbol binario de bsqueda es necesario que en dicho tipo se pueda establecer una relacin de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el rbol en Pascal no se puede establecer una relacin de orden para las claves, puesto que Pascal no admite determinar si un puntero es mayor o menor que otro. En el ejemplo de la figura 5 las claves son nmeros enteros. Dada la raz 4, las claves del subrbol izquierdo son menores que 4, y las claves del subrbol derecho son mayores que 4. Esto se cumple tambin para todos los subrboles. Si se hace el recorrido de este rbol en orden central se obtiene una lista de los nmeros ordenada de menor a mayor. Cuestin: Qu hay que hacer para obtener una lista de los nmeros ordenada de mayor a menor?
27
Una ventaja fundamental de los rboles de bsqueda es que son en general mucho ms rpidos para localizar un elemento que una lista enlazada. Por tanto, son ms rpidos para insertar y borrar elementos. Si el rbol est perfectamente equilibrado -esto es, la diferencia entre el nmero de nodos del subrbol izquierdo y el nmero de nodos del subrbol derecho es a lo sumo 1, para todos los nodos- entonces el nmero de comparaciones necesarias para localizar una clave es aproximadamente de logN en el peor caso. Adems, el algoritmo de insercin en un rbol binario de bsqueda tiene la ventaja -sobre los arrays ordenados, donde se empleara bsqueda dicotmica para localizar un elemento- de que no necesita hacer una reubicacin de los elementos de la estructura para que esta siga ordenada despus de la insercin. Dicho algoritmo funciona avanzando por el rbol escogiendo la rama izquierda o derecha en funcin de la clave que se inserta y la clave del nodo actual, hasta encontrar su ubicacin; por ejemplo, insertar la clave 7 en el rbol de la figura 5 requiere avanzar por el rbol hasta llegar a la clave 8, e introducir la nueva clave en el subrbol izquierdo a 8. El algoritmo de borrado en rboles es algo ms complejo, pero ms eficiente que el de borrado en un array ordenado. Ahora bien, suponer que se tiene un rbol vaco, que admite claves de tipo entero. Suponer que se van a ir introduciendo las claves de forma ascendente. Ejemplo: 1,2,3,4,5,6 Se crea un rbol cuya raz tiene la clave 1. Se inserta la clave 2 en el subrbol derecho de 1. A continuacin se inserta la clave 3 en el subrbol derecho de 2. Continuando las inserciones se ve que el rbol degenera en una lista secuencial, reduciendo drsticamente su eficacia para localizar un elemento. De todas formas es poco probable que se de un caso de este tipo en la prctica. Si las claves a introducir llegan de forma ms o menos aleatoria entonces la implementacin de operaciones sobre un rbol binario de bsqueda que vienen a continuacin son en general suficientes. Existen variaciones sobre estos rboles, como los AVL o Red-Black (no se tratan aqu), que sin llegar a cumplir al 100% el criterio de rbol perfectamente equilibrado, evitan problemas como el de obtener una lista degenerada. Operaciones bsicas sobre rboles binarios de bsqueda - Bsqueda Si el rbol no es de bsqueda, es necesario emplear uno de los recorridos anteriores sobre el rbol para localizarlo. El resultado es idntico al de una bsqueda secuencial. Aprovechando las propiedades del rbol de bsqueda se puede acelerar la localizacin. Simplemente hay que descender a lo largo del rbol a izquierda o derecha dependiendo del elemento que se busca. boolean buscar(tarbol *a, int elem)
28
{ if (a == NULL) return FALSE; else if (a->clave < elem) return buscar(a->der, elem); else if (a->clave > elem) return buscar(a->izq, elem); else return TRUE; } - Insercin La insercin tampoco es complicada. Es ms, resulta practicamente idntica a la bsqueda. Cuando se llega a un rbol vaco se crea el nodo en el puntero que se pasa como parmetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces no se hace nada. void insertar(tarbol **a, int elem) { if (*a == NULL) { *a = (arbol *) malloc(sizeof(arbol)); (*a)->clave = elem; (*a)->izq = (*a)->der = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->der, elem); else if ((*a)->clave > elem) insertar(&(*a)->izq, elem); } - Borrado La operacin de borrado si resulta ser algo ms complicada. Se recuerda que el rbol debe seguir siendo de bsqueda tras el borrado. Pueden darse tres casos, una vez encontrado el nodo a borrar: 1) El nodo no tiene descendientes. Simplemente se borra. 2) El nodo tiene al menos un descendiente por una sola rama. Se borra dicho nodo, y su primer descendiente se asigna como hijo del padre del nodo
29
borrado. Ejemplo: en el rbol de la figura 5 se borra el nodo cuya clave es -1. El rbol resultante es:
3) El nodo tiene al menos un descendiente por cada rama. Al borrar dicho nodo es necesario mantener la coherencia de los enlaces, adems de seguir manteniendo la estructura como un rbol binario de bsqueda. La solucin consiste en sustituir la informacin del nodo que se borra por el de una de las hojas, y borrar a continuacin dicha hoja. Puede ser cualquier hoja? No, debe ser la que contenga una de estas dos claves: la mayor de las claves menores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 2. la menor de las claves mayores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 5. El algoritmo de borrado que se implementa a continuacin realiza la sustitucin por la mayor de las claves menores, (aunque se puede escoger la otra opcin sin prdida de generalidad). Para lograr esto es necesario descender primero a la izquierda del nodo que se va a borrar, y despus avanzar siempre a la derecha hasta encontrar un nodo hoja. A continuacin se muestra grficamente el proceso de borrar el nodo de clave 4:
30
Codificacin: el procedimiento sustituir es el que desciende por el rbol cuando se da el caso del nodo con descencientes por ambas ramas. void borrar(tarbol **a, int elem) { void sustituir(tarbol **a, tarbol **aux); tarbol *aux;
if (*a == NULL) /* no existe la clave */ return; if ((*a)->clave < elem) borrar(&(*a)->der, elem); else if ((*a)->clave > elem) borrar(&(*a)->izq, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->izq == NULL) *a = (*a)->der; else if ((*a)->der == NULL) *a = (*a)->izq; else sustituir(&(*a)->izq, &aux); /* se sustituye por la mayor de las menores */ free(aux); } } Ficheros relacionados Implementacin de algunas de las operaciones sobre rboles binarios. Ejercicio resuelto Escribir una funcin que devuelva el numero de nodos de un rbol binario. Una solucin recursiva puede ser la siguiente: funcion nodos(arbol : tipoArbol) : devuelve entero; inicio si arbol = vacio entonces devolver 0;
31
en otro caso devolver (1 + nodos(subarbol_izq) + nodos(subarbol_der)); fin Adaptarlo para que detecte si un rbol es perfectamente equilibrado o no. Problemas propuestos rboles binarios: OIE 98. (Enunciado) Aplicacin prctica de un rbol Se tiene un fichero de texto ASCII. Para este propsito puede servir cualquier libro electrnico de la librera Gutenberg o Cervantes, que suelen tener varios cientos de miles de palabras. El objetivo es clasificar todas las palabras, es decir, determinar que palabras aparecen, y cuantas veces aparece cada una. Palabras como 'nio'-'nia', 'vengo'-'vienes' etc, se consideran diferentes por simplificar el problema. Escribir un programa, que recibiendo como entrada un texto, realice la clasificacin descrita anteriormente. Ejemplo: Texto: "a b'a c. hola, adios, hola" La salida que produce es la siguiente: a2 adios 1 b1 c1 hola 2 Ntese que el empleo de una lista enlazada ordenada no es una buena solucin. Si se obtienen hasta 20.000 palabras diferentes, por decir un nmero, localizar una palabra cualquiera puede ser, y en general lo ser, muy costoso en tiempo. Se puede hacer una implementacin por pura curiosidad para evaluar el tiempo de ejecucin, pero no merece la pena. La solucin pasa por emplear un rbol binario de bsqueda para insertar las claves. El valor de log(20.000) es aproximadamente de 14. Eso quiere decir que localizar una palabra entre 20.000 llevara en el peor caso unos 14 accesos. El contraste con el empleo de una lista es simplemente abismal. Por supuesto, como se ha comentado anteriormente el rbol no va a estar perfectamente equilibrado, pero nadie escribe novelas manteniendo el orden lexicogrfico (como un diccionario) entre las palabras, asi que no se obtendr nunca un rbol muy degenerado. Lo que est claro es que cualquier evolucin del rbol siempre ser mejor que el empleo de una lista. Por ltimo, una vez realizada la lectura de los datos, slo queda hacer un recorrido en orden central del rbol y se obtendr la solucin pedida en cuestin de segundos.32
Una posible definicin de la estructura rbol es la siguiente: typedef struct tarbol { char clave[MAXPALABRA]; int contador; /* numero de apariciones. Iniciar a 0 */ struct tarbol *izq, *der; } tarbol; ARBOL BINARIO Un rbol Binario es un conjunto finito de Elementos, de nombre Nodos de forma que: El rbol Binario es Vaci si no tiene ningn elemento en el. El rbol Binario contiene un Nodo Raz y los dos que parten de l, llamados Nodo Izquierdo y Nodo Derecho. Los rboles tiene 3 Recorridos Diferentes los cuales son: Pre-Orden In-Orden Post-Orden Pre-Orden Definicin: El Recorrido Pre-Orden lo recorre de la siguiente manera, viaje a travs del rbol Binario desplegando el Contenido en la Raz, despus viaje a travs del Nodo Izquierdo y despus a travs del Nodo Derecho. Detalle: Te mp toma el Valor de la Raz y compara si el rbol tiene algn Elemento, de otra manera Desplegara rbol Vaci y terminara el mtodo. Si el rbol tiene elementos dentro de l, lo recorrer y viajara a travs de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Te mp para de esta manera imprimir el siguiente Elemento correspondiente. In-Orden El Recorrido In-Orden lo recorre de la siguiente manera, viaje a travs del rbol Binario desplegando el Contenido en el Nodo Izquierdo despus la Raz y finalmente viaja a travs del Nodo Derecho.33
Detalle: Te mp toma el Valor de la Raz y compara si el rbol tiene algn Elemento, de otra manera Desplegara rbol Vaci y terminara el mtodo. Si el rbol tiene elementos dentro de l, lo recorrer y viajara a travs de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Te mp para de esta manera imprimir el siguiente Elemento correspondiente. Operaciones bsicas Una tarea muy comn a realizar con un rbol es ejecutar una determinada operacin con cada uno de los elementos del rbol. Esta operacin se considera entonces como un parmetro de una tarea msgeneral que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del rbol. Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden especfico, y pueden considerarse como organizados segn una estructura lineal. De hecho, se simplifica considerablemente la descripcin de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el rbol, segn un cierto orden subyacente. Bsqueda Definicin: La Bsqueda es Similar a todas los Mtodos anteriores de Bsqueda, simplemente efecta un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos. Detalle: El Algoritmo de Bsqueda compara el Elemento a buscar con cada uno de los datos de nuestro rbol, compara si el Elemento con el Nodo Raz, si no se encuentra en la Raz compara Elemento contra la Raz para empezar a viajar por el rbol respectivamente, usa un mtodo similar al anterior hasta encontrar el Elemento. De otra forma la bsqueda es fallida. Un rbol binario puede definirse como un rbol que en cada nodo puede tener como mucho grado 2,es decir, a lo ms 2 hijos. Los hijos suelen denominarse hijo a la izquierda e hijo a la derecha, establecindose de esta forma un orden en el posicionamiento de los mismos. Todas las definiciones bsicas que se dieron para rboles generales permanecen inalteradas sin ms que hacer las particularizaciones correspondientes.En los rboles binarios hay que tener en cuenta el orden izqda-drcha de los hijos.Por ejemplo:los rboles binarios a) y b) de la figura 1(adoptamos el convenio de que los hijos a la izquierda son extrados extendindonos hacia la izquierda y los hijos a la derecha a la derecha) son34
diferentes,puesto que difieren en el nodo 5.El rbol c por convenio se supone igual al b) y no al a). EL TIPO DE DATO ABSTRACTO ARBOL BINARIO. Para construir el TDA Arbol Binario bastara con utilizar las primitivas de los rboles generales pero dado la gran importancia y peculiaridades que tienen este tipo de rboles, construiremos una serie de operaciones especficas. Consideraremos las siguientes: CREAR(e,Ti,Td).Devuelve un rbol cuya raz contiene la etiqueta e asignando como hijo a la izquierda Ti y como hijo a la derecha Td. DESTRUIR(T).Libera los recursos que mantienen el rbol T de forma que para volver a usarlo se debe asignar un nuevo valor con la operacin de creacin rbol binario de bsqueda. Los rboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave nica. Si el rbol est organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subrbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este rbol es un rbol binario de bsqueda. Operaciones bsicas Una tarea muy comn a realizar con un rbol es ejecutar una determinada operacin con cada uno de los elementos del rbol. Esta operacin se considera entonces como un parmetro de una tarea ms general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del rbol. Clasificacin de Arboles Binarios Existen cuatro tipos de rbol binario:. Arbol Binario Distinto. Arbol Binario Similares. Arbol Binario Equivalentes. Arbol Binario Completos. rbol Binario Distinto Se dice que dos rboles binarios son distintos cuando sus estructuras son diferentes.
35
rbol Binario Similar Dos arboles binarios son similares cuando sus estructuras son idnticas, pero la informacin que contienen sus nodos es diferente. rbol Binario Equivalente Son aquellos arboles que son similares y que adems los nodos contienen la misma informacin. Ejemplo: rbol Binario Completo Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subrbol derecho. La idea tras los rboles-B es que los nodos internos deben tener un nmero variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo vara dentro de un nodo. Para que siga mantenindose el nmero de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Un rbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura. Los rboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundario como los discos rgidos. Cada nodo tiene como mximo M hijos. Cada nodo (excepto raz y hojas) tiene como mnimo M/2 hijos. La raz tiene al menos 2 hijos si no es un nodo hoja. Todos los nodos hoja aparecen al mismo nivel. Un nodo no hoja con k hijos contiene k-1 elementos almacenados. Los hijos que cuelgan de la raz (r1, , rm) tienen que cumplir ciertas condiciones: El primero tiene valor menor que r1. El segundo tiene valor mayor que r1 y menor que r2, etc. El ltimo hijo tiene valor mayor que rm.
ALGORITMO36
Podemos encontrar muchas definiciones de algoritmo en los textos de programacin, todas ellas muy similares: Conjunto ordenado y finito de pasos que permite hallar la solucin de un problema. Una secuencia de pasos que conducen a la realizacin de una tarea. Descripcin exacta de la secuencia en que se ha de realizar un conjunto de actividades tendientes a resolver un determinado tipo de problema o procedimiento. Conjunto de sentencias / instrucciones en lenguaje nativo, los cuales expresan la lgica de un programa. Es un sistema por el cual se llega a una solucin, teniendo en cuenta que debe de ser definido, finito y preciso. Toda receta, proceso, rutina, mtodo, procedimiento, tcnica, formula que resuelven un determinado problema. Conjunto de instrucciones concretas y detalladas mediante el cual se consigue una accin determinada. Conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas. Descripcin precisa de una sucesin de instrucciones que permite llevar a cabo un trabajo en un nmero finito de pasos. Un conjunto de smbolos y procedimientos usados en la realizacin de un clculo. Caractersticas: Las caractersticas fundamentales que debe cumplir todo algoritmo son: Ser definido: Sin ambigedad, cada paso del algoritmo debe indicar la accin a realizar sin criterios de interpretacin. Ser finito: Un nmero especfico y numerable de pasos debe componer al algoritmo, el cual deber finalizar al completarlos. Tener cero o ms entradas: Datos son proporcionados a un algoritmo como insumo (o estos son generados de alguna forma) para llevar a cabo las operaciones que comprende. Tener una o ms salidas: Debe siempre devolver un resultado; de nada sirve un algoritmo que hace algo y nunca sabemos que fue. El devolver un resultado no debe ser considerado como nicamente verlos en forma impresa o en37
pantalla, como ocurre con las computadoras. Existen muchos otros mecanismos susceptibles de programacin que no cuentan con una salida de resultados de esta forma. Por salida de resultados debe entenderse todo medio o canal por el cual es posible apreciar los efectos de las acciones del algoritmo. Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada ms ni nada menos que aquello que se requiera para y en su ejecucin. Clasificacin de algoritmos * Algoritmo determinista: en cada paso del algoritmo se determina de forma nica el siguiente paso. * Algoritmo no determinista: deben decidir en cada paso de la ejecucin entre varias alternativas y agotarlas todas antes de encontrar la solucin. Todo algoritmo tiene una serie de caractersticas, entre otras que requiere una serie de recursos, algo que es fundamental considerar a la hora de implementarlos en una mquina. Estos recursos son principalmente: El tiempo: perodo transcurrido entre el inicio y la finalizacin del algoritmo. La memoria: la cantidad (la medida vara segn la mquina) que necesita el algoritmo para su ejecucin. Obviamente, la capacidad y el diseo de la mquina pueden afectar al diseo del algoritmo. En general, la mayora de los problemas tienen un parmetro de entrada que es el nmero de datos que hay que tratar, esto es, N. La cantidad de recursos del algoritmo es tratada como una funcin de N. De esta manera puede establecerse un tiempo de ejecucin del algoritmo que suele ser proporcional a una de las siguientes funciones: 1 : Tiempo de ejecucin constante. Significa que la mayora de las instrucciones se ejecutan una vez o muy pocas. logN : Tiempo de ejecucin logartmico. Se puede considerar como una gran constante. La base del logaritmo (en informtica la ms comn es la base 2) cambia la constante, pero no demasiado. El programa es ms lento cuanto ms crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N 2. N : Tiempo de ejecucin lineal. Un caso en el que N valga 40, tardar el doble que otro en que N valga 20. Un ejemplo sera un algoritmo que lee N nmeros enteros y devuelve la media aritmtica. NlogN : El tiempo de ejecucin es NlogN. Es comn encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencers. Si N se duplica, el tiempo de ejecucin es ligeramente mayor del doble.
38
N2: Tiempo de ejecucin cuadrtico. Suele ser habitual cuando se tratan pares de elementos de datos, como por ejemplo un bucle anidado doble. Si N se duplica, el tiempo de ejecucin aumenta cuatro veces. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo. N3: Tiempo de ejecucin cbico. Como ejemplo se puede dar el de un bucle anidado triple. Si N se duplica, el tiempo de ejecucin se multiplica por ocho. 2N: Tiempo de ejecucin exponencial. No suelen ser muy tiles en la prctica por el elevadsimo tiempo de ejecucin. El problema de la mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrs- es un ejemplo. Si N se duplica, el tiempo de ejecucin se eleva al cuadrado. * Algoritmos polinomiales: aquellos que son proporcionales a Nk. Son en general factibles. * Algoritmos exponenciales: aquellos que son proporcionales a kN. En general son infactibles salvo un tamao de entrada muy reducido. - Notacin O-grande En general, el tiempo de ejecucin es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecucin anteriormente propuestos, adems de la suma de algunos trminos ms pequeos. As, un algoritmo cuyo tiempo de ejecucin sea T = 3N2 + 6N se puede considerar proporcional a N2 . En este caso se dira que el algoritmo es del orden de N2, y se escribe O(N2) Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el nmero de vrtices de ste. La notacin O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementacin del algoritmo, adems de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notacin a un algoritmo es encontrar un lmite superior del tiempo de ejecucin, es decir, el peor caso. A veces ocurre que no hay que prestar demasiada atencin a esto. Conviene diferenciar entre el peor caso y el esperado. Por ejemplo, el tiempo de ejecucin del algoritmo Quick Sort es de O(N2). Sin embargo, en la prctica este caso no se da casi nunca y la mayora de los casos son proporcionales a NlogN. Es por ello que se utiliza esta ltima expresin para este mtodo de ordenacin. Una definicin rigurosa de esta notacin es la siguiente: Una funcin g(N) pertenece a O(f(N)) si y slo si existen las constantes c0 y N0 tales que: |g(N)| = N0. Definicin de rbol
39
Un rbol es una estructura de datos, que puede definirse de forma recursiva como: -Una estructura vaca o - Un elemento o clave de informacin (nodo) ms un nmero finito de estructuras tipo rbol, disjuntos, llamados subrboles. Si dicho nmero de estructuras es inferior o igual a 2, se tiene un rbol binario. Es, por tanto, una estructura no secuencial.Otra definicin nos da el rbol como un tipo de grafo (ver grafos): un rbol es un grafo acclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definicin permite implementar un rbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta seccin no se tratar esta implementacin. Formas de representacin - Mediante un grafo:
Figura 1 - Mediante un diagrama encolumnado:a b d c e f En la computacin se utiliza mucho una estructura de datos, que son los rboles binarios. Estos rboles tienen 0, 1 2 descendientes como mximo. El rbol de la figura anterior es un ejemplo vlido de rbol binario.
Nomenclatura sobre rboles - Raz: es aquel elemento que no tiene antecesor; ejemplo: a. - Rama: arista entre dos nodos. - Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y. - Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y40
se puede llegar a X. - Grado de un nodo: el nmero de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2. - Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d - Nodo interno: aquel que tiene al menos un descendiente. - Nivel: nmero de ramas que hay que recorrer para llegar de la raz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3. - Altura: el nivel ms alto del rbol. En el ejemplo de la figura 1 la altura es 3. - Anchura: es el mayor valor del nmero de nodos que hay en un nivel. En la figura, la anchura es 3. Aclaraciones: se ha denominado a a la raz, pero se puede observar segn la figura que cualquier nodo podra ser considerado raz, basta con girar el rbol. Podra determinarse por ejemplo que b fuera la raz, y a y d los sucesores inmediatos de la raz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuacin es necesaria una jerarqua, es decir, que haya una nica raz. Declaracin de rbol binario Se definir el rbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El rbol vaco se representar con un puntero nulo. Un rbol binario puede declararse de la siguiente manera: typedef struct tarbol { int clave; struct tarbol *izq,*der; } tarbol; Otras declaraciones tambin aaden un enlace al nodo padre, pero no se estudiarn aqu. Recorridos sobre rboles binarios Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto que los rboles no son secuenciales como las listas, hay que buscar estrategias alternativas para visitar todos los nodos. - Recorridos en profundidad: * Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y despus visitar el subrbol izquierdo y una vez visitado, visitar el subrbol derecho. Es un proceso recursivo por naturaleza.41
Si se hace el recorrido en preorden del rbol de la figura 1 las visitas seran en el orden siguiente: a,b,d,c,e,f. void preorden(tarbol *a) { if (a != NULL) { visitar(a); preorden(a->izq); preorden(a->der); } } * Recorrido en inorden u orden central: se visita el subrbol izquierdo, el nodo actual, y despus se visita el subrbol derecho. En el ejemplo de la figura 1 las visitas seran en este orden: b,d,a,e,c,f. void inorden(tarbol *a) { if (a != NULL) { inorden(a->izq); visitar(a); inorden(a->der); } } * Recorrido en postorden: se visitan primero el subrbol izquierdo, despus el subrbol derecho, y por ltimo el nodo actual. En el ejemplo de la figura 1 el recorrido quedara as: d,b,e,f,c,a. void postorden(arbol *a) { if (a != NULL) { postorden(a->izq); postorden(a->der);42
visitar(a); } } La ventaja del recorrido en postorden es que permite borrar el rbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrar el rbol o subrbol que se pasa como parmetro. La razn para hacer esto es que no se debe borrar un nodo y despus sus subrboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido. - Recorrido en amplitud: Consiste en ir visitando el rbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raz), despus los nodos de nivel 2, as hasta que ya no queden ms. Si se hace el recorrido en amplitud del rbol de la figura una visitara los nodos en este orden: a,b,c,d,e,f En este caso el recorrido no se realizar de forma recursiva sino iterativa, utilizando una cola (ver Colas) como estructura de datos auxiliar. El procedimiento consiste en encolar (si no estn vacos) los subrboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola est vaca. En la codificacin que viene a continuacin no se implementan las operaciones sobre colas. void amplitud(tarbol *a) { tCola cola; /* las claves de la cola sern de tipo rbol binario */ arbol *aux;
if (a != NULL) { CrearCola(cola); encolar(cola, a); while (!colavacia(cola)) { desencolar(cola, aux);43
visitar(aux); if (aux->izq != NULL) encolar(cola, aux->izq); if (aux->der != NULL) encolar(cola, aux->der); } } } Por ltimo, considrese la sustitucin de la cola por una pila en el recorrido en amplitud. Qu tipo de recorrido se obtiene? Construccin de un rbol binario Hasta el momento se ha visto la declaracin y recorrido de un rbol binario. Sin embargo no se ha estudiado ningn mtodo para crearlos. A continuacin se estudia un mtodo para crear un rbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays. Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el rbol viendo sus recorridos pero sin haber visto el rbol terminado. Partiendo de los recorridos preorden e inorden del rbol de la figura 1 puede determinarse que la raz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raz forman el subrbol izquierdo. Asimismo los elementos entre der y la raz forman el subrbol derecho. Por tanto se tiene este rbol:
A continuacin comienza un proceso recursivo. Se procede a crear el subrbol izquierdo, cuyo tamao est limitado por los ndices izq y der. La siguiente posicin en el recorrido en preorden es la raz de este subrbol. Queda esto:44
El subrbol b tiene un subrbol derecho, que no tiene ningn descendiente, tal y como indican los ndices izq y der. Se ha obtenido el subrbol izquierdo completo de la raz a, puesto que b no tiene subrbol izquierdo:
Despus seguir construyndose el subrbol derecho a partir de la raz a. La implementacin de la construccin de un rbol partiendo de los recorridos en preorden y en inorden puede consultarse aqu (en C). rbol binario de bsqueda Un rbol binario de bsqueda es aquel que es:
45
- Una estructura vaca o - Un elemento o clave de informacin (nodo) ms un nmero finito -a lo sumo dos- de estructuras tipo rbol, disjuntos, llamados subrboles y adems cumplen lo siguiente: * Todas las claves del subrbol izquierdo al nodo son menores que la clave del nodo. * Todas las claves del subrbol derecho al nodo son mayores que la clave del nodo. * Ambos subrboles son rboles binarios de bsqueda. Un ejemplo de rbol binario de bsqueda:
Figura 5 Al definir el tipo de datos que representa la clave de un nodo dentro de un rbol binario de bsqueda es necesario que en dicho tipo se pueda establecer una relacin de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el rbol en Pascal no se puede establecer una relacin de orden para las claves, puesto que Pascal no admite determinar si un puntero es mayor o menor que otro. En el ejemplo de la figura 5 las claves son nmeros enteros. Dada la raz 4, las claves del subrbol izquierdo son menores que 4, y las claves del subrbol derecho son mayores que 4. Esto se cumple tambin para todos los subrboles. Si se hace el recorrido de este rbol en orden central se obtiene una lista de los nmeros ordenada de menor a mayor. Cuestin: Qu hay que hacer para obtener una lista de los nmeros ordenada de mayor a menor? Una ventaja fundamental de los rboles de bsqueda es que son en general mucho ms rpidos para localizar un elemento que una lista enlazada. Por tanto, son ms rpidos para insertar y borrar elementos. Si el rbol46
est perfectamente equilibrado -esto es, la diferencia entre el nmero de nodos del subrbol izquierdo y el nmero de nodos del subrbol derecho es a lo sumo 1, para todos los nodos- entonces el nmero de comparaciones necesarias para localizar una clave es aproximadamente de logN en el peor caso. Adems, el algoritmo de insercin en un rbol binario de bsqueda tiene la ventaja -sobre los arrays ordenados, donde se empleara bsqueda dicotmica para localizar un elemento- de que no necesita hacer una reubicacin de los elementos de la estructura para que esta siga ordenada despus de la insercin. Dicho algoritmo funciona avanzando por el rbol escogiendo la rama izquierda o derecha en funcin de la clave que se inserta y la clave del nodo actual, hasta encontrar su ubicacin; por ejemplo, insertar la clave 7 en el rbol de la figura 5 requiere avanzar por el rbol hasta llegar a la clave 8, e introducir la nueva clave en el subrbol izquierdo a 8. El algoritmo de borrado en rboles es algo ms complejo, pero ms eficiente que el de borrado en un array ordenado. Ahora bien, suponer que se tiene un rbol vaco, que admite claves de tipo entero. Suponer que se van a ir introduciendo las claves de forma ascendente. Ejemplo: 1,2,3,4,5,6 Se crea un rbol cuya raz tiene la clave 1. Se inserta la clave 2 en el subrbol derecho de 1. A continuacin se inserta la clave 3 en el subrbol derecho de 2. Continuando las inserciones se ve que el rbol degenera en una lista secuencial, reduciendo drsticamente su eficacia para localizar un elemento. De todas formas es poco probable que se de un caso de este tipo en la prctica. Si las claves a introducir llegan de forma ms o menos aleatoria entonces la implementacin de operaciones sobre un rbol binario de bsqueda que vienen a continuacin son en general suficientes. Existen variaciones sobre estos rboles, como los AVL o Red-Black (no se tratan aqu), que sin llegar a cumplir al 100% el criterio de rbol perfectamente equilibrado, evitan problemas como el de obtener una lista degenerada. Operaciones bsicas sobre rboles binarios de bsqueda - Bsqueda Si el rbol no es de bsqueda, es necesario emplear uno de los recorridos anteriores sobre el rbol para localizarlo. El resultado es idntico al de una bsqueda secuencial. Aprovechando las propiedades del rbol de bsqueda se puede acelerar la localizacin. Simplemente hay que descender a lo largo del rbol a izquierda o derecha dependiendo del elemento que se busca. boolean buscar(tarbol *a, int elem) { if (a == NULL) return FALSE;
47
else if (a->clave < elem) return buscar(a->der, elem); else if (a->clave > elem) return buscar(a->izq, elem); else return TRUE; } - Insercin La insercin tampoco es complicada. Es ms, resulta practicamente idntica a la bsqueda. Cuando se llega a un rbol vaco se crea el nodo en el puntero que se pasa como parmetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces no se hace nada. void insertar(tarbol **a, int elem) { if (*a == NULL) { *a = (arbol *) malloc(sizeof(arbol)); (*a)->clave = elem; (*a)->izq = (*a)->der = NULL; } else if ((*a)->clave < elem) insertar(&(*a)->der, elem); else if ((*a)->clave > elem) insertar(&(*a)->izq, elem); } - Borrado La operacin de borrado si resulta ser algo ms complicada. Se recuerda que el rbol debe seguir siendo de bsqueda tras el borrado. Pueden darse tres casos, una vez encontrado el nodo a borrar: 1) El nodo no tiene descendientes. Simplemente se borra. 2) El nodo tiene al menos un descendiente por una sola rama. Se borra dicho nodo, y su primer descendiente se asigna como hijo del padre del nodo borrado. Ejemplo: en el rbol de la figura 5 se borra el nodo cuya clave es -1. El rbol resultante es:
48
3) El nodo tiene al menos un descendiente por cada rama. Al borrar dicho nodo es necesario mantener la coherencia de los enlaces, adems de seguir manteniendo la estructura como un rbol binario de bsqueda. La solucin consiste en sustituir la informacin del nodo que se borra por el de una de las hojas, y borrar a continuacin dicha hoja. Puede ser cualquier hoja? No, debe ser la que contenga una de estas dos claves: la mayor de las claves menores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 2. la menor de las claves mayores al nodo que se borra. Suponer que se quiere borrar el nodo 4 del rbol de la figura 5. Se sustituir la clave 4 por la clave 5. El algoritmo de borrado que se implementa a continuacin realiza la sustitucin por la mayor de las claves menores, (aunque se puede escoger la otra opcin sin prdida de generalidad). Para lograr esto es necesario descender primero a la izquierda del nodo que se va a borrar, y despus avanzar siempre a la derecha hasta encontrar un nodo hoja. A continuacin se muestra grficamente el proceso de borrar el nodo de clave 4:
Codificacin: el procedimiento sustituir es el que desciende por el rbol cuando se da el caso del nodo con descencientes por ambas ramas. void borrar(tarbol **a, int elem)49
{ void sustituir(tarbol **a, tarbol **aux); tarbol *aux;
if (*a == NULL) /* no existe la clave */ return; if ((*a)->clave < elem) borrar(&(*a)->der, elem); else if ((*a)->clave > elem) borrar(&(*a)->izq, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->izq == NULL) *a = (*a)->der; else if ((*a)->der == NULL) *a = (*a)->izq; else sustituir(&(*a)->izq, &aux); /* se sustituye por la mayor de las menores */ free(aux); } } Ficheros relacionados Implementacin de algunas de las operaciones sobre rboles binarios. Ejercicio resuelto Escribir una funcin que devuelva el numero de nodos de un rbol binario. Una solucin recursiva puede ser la siguiente: funcion nodos(arbol : tipoArbol) : devuelve entero; inicio si arbol = vacio entonces devolver 0; en otro caso devolver (1 + nodos(subarbol_izq) + nodos(subarbol_der)); fin Adaptarlo para que detecte si un rbol es perfectamente equilibrado o no. Problemas propuestos50
rboles binarios: OIE 98. (Enunciado) Aplicacin prctica de un rbol Se tiene un fichero de texto ASCII. Para este propsito puede servir cualquier libro electrnico de la librera Gutenberg o Cervantes, que suelen tener varios cientos de miles de palabras. El objetivo es clasificar todas las palabras, es decir, determinar que palabras aparecen, y cuantas veces aparece cada una. Palabras como 'nio'-'nia', 'vengo'-'vienes' etc, se consideran diferentes por simplificar el problema. Escribir un programa, que recibiendo como entrada un texto, realice la clasificacin descrita anteriormente. Ejemplo: Texto: "a b'a c. hola, adios, hola" La salida que produce es la siguiente: a2 adios 1 b1 c1 hola 2 Ntese que el empleo de una lista enlazada ordenada no es una buena solucin. Si se obtienen hasta 20.000 palabras diferentes, por decir un nmero, localizar una palabra cualquiera puede ser, y en general lo ser, muy costoso en tiempo. Se puede hacer una implementacin por pura curiosidad para evaluar el tiempo de ejecucin, pero no merece la pena. La solucin pasa por emplear un rbol binario de bsqueda para insertar las claves. El valor de log(20.000) es aproximadamente de 14. Eso quiere decir que localizar una palabra entre 20.000 llevara en el peor caso unos 14 accesos. El contraste con el empleo de una lista es simplemente abismal. Por supuesto, como se ha comentado anteriormente el rbol no va a estar perfectamente equilibrado, pero nadie escribe novelas manteniendo el orden lexicogrfico (como un diccionario) entre las palabras, asi que no se obtendr nunca un rbol muy degenerado. Lo que est claro es que cualquier evolucin del rbol siempre ser mejor que el empleo de una lista. Por ltimo, una vez realizada la lectura de los datos, slo queda hacer un recorrido en orden central del rbol y se obtendr la solucin pedida en cuestin de segundos. Una posible definicin de la estructura rbol es la siguiente: typedef struct tarbol {
51
char clave[MAXPALABRA]; int contador; /* numero de apariciones. Iniciar a 0 */ struct tarbol *izq, *der; } tarbol; ARBOL BINARIO Un rbol Binario es un conjunto finito de Elementos, de nombre Nodos de forma que: El rbol Binario es Vaci si no tiene ningn elemento en el. El rbol Binario contiene un Nodo Raz y los dos que parten de l, llamados Nodo Izquierdo y Nodo Derecho. Los rboles tiene 3 Recorridos Diferentes los cuales son: Pre-Orden In-Orden Post-Orden Pre-Orden Definicin: El Recorrido Pre-Orden lo recorre de la siguiente manera, viaje a travs del rbol Binario desplegando el Contenido en la Raz, despus viaje a travs del Nodo Izquierdo y despus a travs del Nodo Derecho. Detalle: Te mp toma el Valor de la Raz y compara si el rbol tiene algn Elemento, de otra manera Desplegara rbol Vaci y terminara el mtodo. Si el rbol tiene elementos dentro de l, lo recorrer y viajara a travs de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Te mp para de esta manera imprimir el siguiente Elemento correspondiente. In-Orden El Recorrido In-Orden lo recorre de la siguiente manera, viaje a travs del rbol Binario desplegando el Contenido en el Nodo Izquierdo despus la Raz y finalmente viaja a travs del Nodo Derecho. Detalle: Te mp toma el Valor de la Raz y compara si el rbol tiene algn Elemento, de otra manera Desplegara rbol Vaci y terminara el mtodo. Si el rbol52
tiene elementos dentro de l, lo recorrer y viajara a travs de los Arreglos Izq y Der para determinar que valor meter en la Pila y en Te mp para de esta manera imprimir el siguiente Elemento correspondiente. Operaciones bsicas Una tarea muy comn a realizar con un rbol es ejecutar una determinada operacin con cada uno de los elementos del rbol. Esta operacin se considera entonces como un parmetro de una tarea msgeneral que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del rbol. Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden especfico, y pueden considerarse como organizados segn una estructura lineal. De hecho, se simplifica considerablemente la descripcin de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el rbol, segn un cierto orden subyacente. Bsqueda Definicin: La Bsqueda es Similar a todas los Mtodos anteriores de Bsqueda, simplemente efecta un recorrido comparando el Elemento que deseas encontrar contra cada uno de los Elementos en los Arreglos. Detalle: El Algoritmo de Bsqueda compara el Elemento a buscar con cada uno de los datos de nuestro rbol, compara si el Elemento con el Nodo Raz, si no se encuentra en la Raz compara Elemento contra la Raz para empezar a viajar por el rbol respectivamente, usa un mtodo similar al anterior hasta encontrar el Elemento. De otra forma la bsqueda es fallida. Un rbol binario puede definirse como un rbol que en cada nodo puede tener como mucho grado 2,es decir, a lo ms 2 hijos. Los hijos suelen denominarse hijo a la izquierda e hijo a la derecha, establecindose de esta forma un orden en el posicionamiento de los mismos. Todas las definiciones bsicas que se dieron para rboles generales permanecen inalteradas sin ms que hacer las particularizaciones correspondientes.En los rboles binarios hay que tener en cuenta el orden izqda-drcha de los hijos.Por ejemplo:los rboles binarios a) y b) de la figura 1(adoptamos el convenio de que los hijos a la izquierda son extrados extendindonos hacia la izquierda y los hijos a la derecha a la derecha) son diferentes,puesto que difieren en el nodo 5.El rbol c por convenio se supone igual al b) y no al a). EL TIPO DE DATO ABSTRACTO53
ARBOL BINARIO. Para construir el TDA Arbol Binario bastara con utilizar las primitivas de los rboles generales pero dado la gran importancia y peculiaridades que tienen este tipo de rboles, construiremos una serie de operaciones especficas. Consideraremos las siguientes: CREAR(e,Ti,Td).Devuelve un rbol cuya raz contiene la etiqueta e asignando como hijo a la izquierda Ti y como hijo a la derecha Td. DESTRUIR(T).Libera los recursos que mantienen el rbol T de forma que para volver a usarlo se debe asignar un nuevo valor con la operacin de creacin rbol binario de bsqueda. Los rboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave nica. Si el rbol est organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subrbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este rbol es un rbol binario de bsqueda. Operaciones bsicas Una tarea muy comn a realizar con un rbol es ejecutar una determinada operacin con cada uno de los elementos del rbol. Esta operacin se considera entonces como un parmetro de una tarea ms general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del rbol. Clasificacin de Arboles Binarios Existen cuatro tipos de rbol binario:. Arbol Binario Distinto. Arbol Binario Similares. Arbol Binario Equivalentes. Arbol Binario Completos. rbol Binario Distinto Se dice que dos rboles binarios son distintos cuando sus estructuras son diferentes. rbol Binario Similar Dos arboles binarios son similares cuando sus estructuras son idnticas, pero la informacin que contienen sus nodos es diferente.
54
rbol Binario Equivalente Son aquellos arboles que son similares y que adems los nodos contienen la misma informacin. Ejemplo: rbol Binario Completo Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subrbol derecho. La idea tras los rboles-B es que los nodos internos deben tener un nmero variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo vara dentro de un nodo. Para que siga mantenindose el nmero de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Un rbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura. Los rboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da usualmente cuando los nodos se encuentran en dispositivos de almacenamiento secundario como los discos rgidos. Cada nodo tiene como mximo M hijos. Cada nodo (excepto raz y hojas) tiene como mnimo M/2 hijos. La raz tiene al menos 2 hijos si no es un nodo hoja. Todos los nodos hoja aparecen al mismo nivel. Un nodo no hoja con k hijos contiene k-1 elementos almacenados. Los hijos que cuelgan de la raz (r1, , rm) tienen que cumplir ciertas condiciones: El primero tiene valor menor que r1. El segundo tiene valor mayor que r1 y menor que r2, etc. El ltimo hijo tiene valor mayor
GrafosSoftware para la construccin, edicin y anlisis de grafos. Este software pretende ser de utilidad para la docencia y el aprendizaje de la teora de grafos (graph theory), y otras disciplinas relacionadas como la ingeniera de organizacin industrial, la logstica y el transporte, investigacin55
operativa, el diseo de redes, etc. Grafos se puede usar perfectamente para el modelado y resolucin de problemas reales de cierto tamao y complejidad. Un grafo representa un modelo de una realidad empresarial en forma de red. Este modelo podr ser analizado desde distintos puntos de vista gracias a los algoritmos y funciones incorporados en el software Grafos. Independientemente de sus conocimientos actuales sobre la materia, la informacin recogida en estas pginas y el libro sern un buen punto de partida para el aprendizaje en mayor profundidad de la teora de grafos y su aplicacin en la realidad empresarial e industrial.
la idea
La filosofa de Grafos es la siguiente: dibujar, modelar, resolver y analizar. Con esto se pretende que el usuario tenga libertad absoluta para tratar y abordar los problemas de grafos. Usted podr dibujar libremente el grafo sin preocuparse del anlisis o algoritmo que utilizar posteriormente. Grafos le avisar en caso de no factibilidad o de cualquier otro requerimiento para un anlisis en particular. Los estudiantes que usen Grafos experimentarn un proceso de aprendizaje basado en su libertad y en etapas de prueba-error. Esa libertad en la utilizacin56
del programa y su filosofa de aprendizaje, fue la idea inicial y la inquietud que origin este proyecto. Otros programas existentes guan al usuario paso a paso, descartando de entrada su libertad de eleccin y construccin.el proyecto
Grafos comenz en el ao 2003 como parte de un proyecto de investigacin y desarrollo de aplicaciones informticas de diseo modular orientadas hacia la docencia, la investigacin y las labores profesionales de ingeniera de organizacin industrial. El desarrollo est orientado hacia los siguientes objetivos:
Desarrollar un interfaz para la construccin y edicin de grafos en modo tabular o grfico, y que permita la incorporacin modular de multitud de funciones. Desarrollar una estructura de clases y libreras .dll con un conjunto de algoritmos de resolucin de diferentes problemas de teora de grafos. Redactar y publicar un completo manual de usuario actualizado a la ltima versin disponible.
Actualmente, el proyecto Grafos sigue en activo, en proceso de programacin de nuevos algoritmos, la incorporacin de nuevas funciones y la redaccin de documentacin actualizada. Si lo desea puede conocer el estado del desarrollo, sumarse a este proyecto compartiendo el desarrollo y otras experiencias relacionadas.
TEORIA DE GRAFICASINTRODUCCINLa teora de grficas o teora de grafos es aplicada en una gran cantidad de reas tales como ciencias sociales, lingstica, ciencias fsicas, ingeniera de comunicacin, y otras. La teora de grafos tambin juega un papel importante en varias reas de la ciencia de la computacin, tales como teora de cambio y lgica de diseo, inteligencia artificial, lenguajes formales, grficos por computadora, sistemas operativos, compiladores, y organizacin y recuperacin de informacin.
CONCEPTOS BSICOS DE LA TEORIA DE GRAFOS
La terminologa usada en la teora de grafos no es estndar. No es poco usual encontrar que varios trminos diferentes son usados como sinnimos. Esta situacin, de cualquier manera, llega a ser ms complicada cuando descubrimos que un trmino en particular es usado por diferentes autores para referirse a conceptos desiguales. Esta situacin es natural debido a la gran diversidad de campos en los que la teora de grficas se aplica. En esta seccin debemos definir un grafo como un sistema matemtico abstracto. De cualquier manera, para dar algo de sentido a la terminologa usada y tambin para57
desarrollar algunas ideas intuitivas, se representar un grafo por medio de un diagrama. Ese diagrama se llamar igualmente grafo. Las definiciones y trminos aqu presentados no estn restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso ya que estos trminos tengan una fuerte asociacin con dicha representacin. Debemos resaltar que una representacin diagramtica es posible nicamente en casos muy simples. Los mtodos alternativos para representar grafos sern igualmente discutidos. Definiciones bsicas Primeramente se consideraran varios grafos que son presentados por medio de diagramas. Algunos de estos grafos pueden ser considerados como grafos de cierta relacin, pero hay algunos otros que no pueden ser interpretados de esta manera. Considrese el diagrama de la figura 1.1. Para el propsito de nuestro estudio, estos diagramas representarn grafos. Ntese que cada diagrama consiste de un conjunto de elementos que son representados por puntos o crculos y estn en ocasiones etiquetados como v1, v2,..., o 1,2,.... Tambin, en cada diagrama ciertas parejas de dichos puntos estn conectados por lneas o arcos. Definicin. Un grafo G = V,E, consiste de un conjunto V no vaci llamado el conjunto de nodos (puntos, vrtices) del grafo, donde E es el conjunto de los ejes del grafo, y es un mapeo del conjunto de ejes E a un conjunto ordenado o desordenado de elementos pares de V. Debemos asumir de lo anterior que ambos, los conjuntos V y E de un grafo son finitos. Sera conveniente denotar un grafo G como V,E , o simplemente como G. Ntese que la definicin de grafo implica que para cada eje del grafo G podemos asociar una pareja ordenada o no ordenada de nodos pertenecientes al grafo. Si un eje x E est asociado con un par ordenado (u, v) o un par no ordenado (u, v), donde u,vV , entonces se dice que el eje x conecta o une los nodos u y v. Cualquier par de nodos que estn conectados por un eje en un grafo son llamados nodos adyacentes. Definicin. En un grafo G = (V,E), un eje que est asociado a un par ordenado de V x V es
58
llamado eje dirigido de G, mientras un eje que est asociado a un par no ordenado de nodos es llamado eje no dirigido. Un grafo del cual cada nodo es dirigido es llamado dgrafo o grafo dirigido. Un grafo en el cual cada eje es no dirigido es llamado grafo no dirigido. Si algunos ejes son dirigidos y otros no dirigidos en un grafo, se trata de un grafo mixto.
Trayectorias, Alcances y ConectividadSea G = (V , E) un grafo dirigido simple. Considerando una secuencia de ejes de G tal que el nodo terminal de cada eje en la secuencia es el nodo inicial del siguiente eje, si existe alguno en la secuencia. Un ejemplo de secuencia de este tipo es: ((vi1,vi2 ),(vi2 ,vi3),...,(vik 2 ,vik 1),(vik 1,vik )) Definicin: Cualquier secuencia de ejes de un grafo dirigido tal que el nodo terminal de cada eje en la secuencia es el nodo inicial de otro eje, si existe, siendo el siguiente en la secuencia define la trayectoria de un grafo. Una trayectoria se define como un viaje a travs de los nodos que aparecen en la secuencia, y que se origina en el nodo inicial del primer eje y finaliza en el nodo terminal del ltimo eje de la secuencia. Definicin: El nmero de ejes que aparecen en la secuencia de una trayectoria es llamado longitud de la trayectoria.
EL MODELO DEL SISTEMAUn sistema consiste de un nmero finito de recursos que son distribuidos entre un nmero de procesos que compiten por ellos. Los recursos son clasificados en diferentes tipos, cada uno de los cuales consiste de algn nmero de instancias iguales a. Ciclos de CPU b. Espacio en memoria c. Archivos y dispositivos de E/S (tales como impresoras, unidades de cinta y de disco, etc.) son ejemplos de tipos de recursos. Si un sistema tiene dos CPU's, entonces el tipo CPU tiene dos instancias. Un proceso debe solicitar un recurso antes de usarlo y liberarlo despus de usarlo.59
Un proceso puede solicitar tantos recursos como sean necesarios para llevar a cabo la tarea para la cual ha sido diseado. Obviamente el nmero de recursos solicitados no debe exceder el nmero de recursos disponibles en el sistema. En otras palabras, un proceso no debe pedir tres impresoras si en el sistema solo existen dos. Bajo un modo normal de operacin un proceso puede utilizar un recurso slo en la siguiente secuencia: 1.- PETICIN. Si la peticin no puede ser satisfecha inmediatamente (por ejemplo, el recurso esta siendo utilizado por otro proceso), entonces el proceso solicitante debe esperar hasta que pueda adquirir el recurso. 2.- USO. El proceso puede utilizar un recurso (por ejemplo, si el recurso es una impresora en lnea, el proceso puede imprimir en la impresora). 3.- LIBERACIN. El proceso libera el recurso. La peticin y liberacin del recurso son peticiones al sistema. El uso de recursos puede tambin hacerse solo a travs de llamadas al sistema. Por lo tanto, para cada uso, el sistema operativo checa para asegurarse de que el proceso usuario ha pedido y se le han asignado los recursos. Una tabla del sistema registra cuando un recurso est libre o asignado, y si est asignado, a que proceso. Si un proceso pide un recurso que est asignado en ese momento a otro proceso, ste puede ser agregado a una cola de procesos en espera de ese recurso.
DEFINICIN DE ABRAZO MORTALUn conjunto de procesos est en un abrazo mortal cuando todos los procesos en ese conjunto estn esperando un evento que slo puede ser causado por otro proceso en el conjunto. Los eventos a que nos referimos son concernientes con la asignacin y liberacin de recursos principalmente. Sin embargo, otro tipo de eventos pueden llevar a la existencia de abrazos mortales. Los abrazos mortales pueden tambin involucrar diferentes tipos de recursos. Por ejemplo, considere un sistema con una impresora y una unidad de disco. Suponga que el proceso P tiene asignada la unidad de disco y que el proceso Q tiene asignada la impresora. Ahora, si P pide la impresora y Q pide la unidad de disco, ocurre un abrazo mortal.
CARACTERIZACIN DE UN ABRAZO MORTAL60
Un abrazo mortal es una condicin indeseable. En un abrazo mortal, los procesos nunca terminan de ejecutarse y los recursos del sistema esta amarrados, evitando que otros procesos puedan siquiera empezar.
CONDICIONES NECESARIASUna situacin de abrazo mortal puede surgir s y solo s las siguientes cuatro condiciones ocurren simultneamente en un sistema. _ Exclusin Mutua. Al menos un recurso es mantenido en un modo no-compartible; esto es, slo un proceso a la vez puede usar el recurso. Si otro proceso solicita ese recurso, tiene que ser retardado hasta que el recurso haya sido liberado. _ Retener y esperar. Debe existir un proceso que retenga al menos un recurso y est esperando para adquirir recursos adicionales que estn siendo retenidos por otros procesos. _ No existe el derecho de desasignar (No preemption). Los recursos no pueden ser desasignados (preempted); esto es, un recurso slo puede ser liberado voluntariamente por el proceso que lo retiene, despus de que el proceso ha terminado su tarea. _ Espera Circular. Debe existir un conjunto {p0, p1, ...,pn} de procesos en espera tal que p0 est esperando por un recurso que est siendo retenido por p1, p1 est esperando por un recurso que est siendo retenido por p2, ..., pn-1 est esperando por un recurso que est siendo retenido por pn y pn est esperando por un recurso que est siendo retenido por p0.
MTODOS PARA MANEJAR LOS ABRAZOS MORTALESExisten dos mtodos para manejar el problema de los abrazos mortales. Podemos usar algn protocolo para asegurar que el sistema nunca entrar en un estado de abrazo mortal podemos permitir que el sistema entre en un estado de abrazo mortal y despus recuperarnos. El recuperarse de un abrazo mortal puede ser muy difcil y muy caro. Por ello, primeramente consideraremos los mtodos para asegurar que no ocurran los abrazos mortales. Comnmente, existen dos mtodos: PREVENCIN de abrazos mortales (Deadlock Prevention) EVASIN de abrazos mortales (Deadlock Avoidance). PREVENCIN DE ABRAZOS MORTALES.61
Para que ocurra un abrazo mortal, deben presentarse cada una de las cuatro condiciones necesarias. Al asegurarnos de que por lo menos una de estas condiciones no se presente, podemos prevenir la ocurrencia de un abrazo mortal. Examinando cada una de las condiciones necesarias por separado.
A. EXCLUSIN MUTUA.La condicin de exclusin mutua debe mantenerse para los tipos de recursos que no son compartibles. Por ejemplo, una impresora no puede ser compartida simultneamente por varios procesos. En general, no es posible prevenir los abrazos mortales negando la condicin de exclusin mutua, debido a que algunos recursos son intrnsecamente no compartibles.
B.RETENER Y ESPERAR.Para asegurar que la condicin de retener y esperar nunca ocurra en el sistema, se debe garantizar que siempre que un proceso solicite un recurso, este no pueda retener otros recursos. Un protocolo que puede ser usado requiere que cada proceso solicite y le sean asignados todos los recursos antes de que empiece su ejecucin.
NO EXISTE EL DERECHO DE DESASIGNARLa tercera condicin necesaria es que no debe de existir el derecho de desasignar recursos que han sido previamente asignados. Con el fin de asegurar que esta condicin no se cumple, el siguiente protocolo puede ser usado. Si un proceso que esta reteniendo algunos recursos solicita otro recurso que no puede ser asignado inmediatamente (esto es, que el proceso tenga que esperar), entonces todos los recursos que tiene este proceso en espera son desasginados. Esto es, los recursos son liberados implcitamente. Los recursos liberados son agregados a la lista de los recursos por los cuales esta esperando el proceso. El proceso solo puede volver a ser reinicializado cuando haya obtenido otra vez todos los recursos que tenia asignados, as como el nuevo recurso que estaba solicitando. Alternativamente si un proceso solicita algunas recursos, primero verificamos si estos estn disponibles. Si es as, entonces se le asignan. De otro modo, se verifica si estn asignados a alguno de los procesos que estn en espera de recursos adicionales. Si es as, los recursos deseados son desasginados del proceso en espera y asignados al proceso solicitante. De otra manera (no estn62
disponibles, ni asignados a procesos en espera) el proceso que hace la solicitud debe esperar. Pero, mientras esta esperando, algunos de sus recursos pueden ser desasignados solamente si estos son solicitados. Un proceso puede ser reinicializado cuando se le asigna el recurso que haba solicitado y recupera cualquier recurso que haya sido desasignado mientras esperaba.
ESPERA CIRCULARCon el fin de asegurarse de que la condicin de espera circular nunca se presente, se puede imponer un ordenamiento total sobre todos los tipos de recursos. Esto es, asignamos a cada tipo de recurso un nmero entero nico, el cual permita comparar dos recursos y determinar cuando uno precede al otro en el ordenamiento. Mas formalmente, sea R={r1,r2,...,rn} el conjunto de tipos de recursos. Puede definirse una funcin uno a uno F:R->N, donde N es el conjunto de nmeros naturales. Por ejemplo, si el conjunto R de tipos de recursos incluye unidades de disco (UDD), unidades de cinta (UDC), lectoras pticos (LO) e impresoras (I), entonces la funcin F puede ser definida como sigue: F(LO) =1 F(UDD) = 5 F(UDC) = 7 F(I) = 12 Se puede considerar el siguiente protocolo para prevenir abrazos mortales: Cada proceso puede solicitar recursos solamente en un orden creciente de numeracin. Esto es un proceso puede solicitar inicialmente cualquier numero de instancias de un tipo de recurso, digamos ri. Despus de esto, el proceso puede solicitar instancias de recursos del tipo rj si y solo si F(rj) > F(ri). Si varias instancias del mismo tipo de recurso son necesitadas, debe hacerse una sola peticin para todas las instancias debe ser usada. Por ejemplo, usando la funcin definida anteriormente, un proceso que quiere usar el lector ptico (LO) y la impresora (I) debe solicitar primero el (LO) y despus la (I). Alternativamente, se puede requerir simplemente que siempre que un proceso solicite una instancia del recurso tipo rj, este tenga que liberar cualquier recurso del tipo ri tal que F(ri) >= F(rj). Si este protocolo es usado, la condicin de cola circular no puede presentarse. Se puede demostrar este hecho asumiendo que existe una cola circular (prueba por contradiccin). Sea {p0, p2, p2, ..., pn} el conjunto de procesos que estn en la espera circular, donde pi esta esperando por un recurso ri, el cual es retenido por pi+1. (Aplicando modulo aritmtico sobre los ndices, pn esta esperando por un recurso rn que esta siendo retenido por p0). Entonces, debido a que el proceso pi+1 esta reteniendo el recurso ri mientras esta esperando el recurso ri+1, se debe de tener F(ri) < F(ri+1), para toda i. Pero esto significa que F(r0) < F(r1) < ... < F(rn) < F(r0). Por transitividad, F(r0) < F(r0), lo cual es imposible. Por lo tanto, no puede existir una espera circular. Debe notarse que la funcin F debe definirse de acuerdo al63
ordenamiento de uso normal de los recursos en el sistema. Por ejemplo, usualmente se utiliza primero una (UDD) antes que la (I), por lo cual es razonable definir F(UDD) < F(i). EVASIN DE ABRAZOS MORTALES Los algoritmos de prevencin de abrazos mortales, como se discuti anteriormente, los previenen al restringir la manera en que se hacen las solicitudes. Las restricciones aseguran que al menos una de las condiciones necesarias no se presentar. Sin embargo, un efecto colateral de prevenir los abrazos mortales por este mtodo es la posible baja utilizacin de los recursos y el reducido desempeo del sistema. Un mtodo alternativo para evitar los abrazos mortales requiere de informacin adicional acerca de cmo van a ser solicitados los recursos. Por ejemplo, en un sistema con una lectora ptica y una impresora, pudiera ser que se dijera que el proceso P solicitar la lectora ptica y despus la impresora, antes de liberar ambos recursos. El proceso Q, por otro lado, solicitar primero la impresora y despus la lectora ptica. Con este conocimiento de la secuencia completa de peticiones y liberaciones de cada proceso, se puede decidir para cada peticin si el proceso debe esperar o no. Cada solicitud requiere que el sistema considere los recursos actualmente disponibles, los recursos actualmente asignados a cada proceso y las solicitudes y liberaciones futuras de cada proceso, para decidir si la solicitud actual puede satisfacerse o debe esperar para satisfacer un posible abrazo mortal futuro. Existen varios algoritmos que difieren en la cantidad y tipo de informacin que requieren. El modelo mas sencillo y mas til requiere que cada proceso declare el mximo nmero de recursos de cada tipo que pudiera necesitar. Dada esta informacin a priori, para cada proceso, acerca del mximo nmero de recursos de cada tipo que puedan llegar a necesitar, es posible construir un algoritmo que asegure que el sistema nunca entrar en un estado de abrazo mortal. Este algoritmo define la aproximacin de evasin de abrazos mortales. Un algoritmo de evasin de abrazos mortales dinmicamente examina el estado de asignacin de recursos para asegurarse que nunca pueda existir una condicin de espera circular. El estado de asignacin de los recursos es definido por el nmero de recursos disponibles, asignados y la demanda mxima de los procesos. Un estado es seguro si el sistema puede asignar recursos a cada proceso (hasta su mximo) en algn orden y an puede evitar un abrazo mortal. Mas formalmente, un sistema est en un estado seguro solo si existe una secuencia segura. Una secuencia de procesos es una secuencia segura para el estado actual de asignacin si para cada pi, las solicitudes por recursos que pi puede aun solicitar pueden ser satisfechas con los recursos actualmente disponibles mas los recursos retenidos por todos los pj, con jindex hacer A[j+1] = A[j] j=j-1 fin mientras A[j+1] = index fin para fin algoritmo
Aunque este algoritmo tiene un mejor orden de complejidad que el de burbuja, es muy ineficiente al compararlo con otros algoritmos como quicksort. Sin embargo, para listas relativamente pequeas el orden por insercin es una buena eleccin, no slo porque puede ser ms rpido para cantidades pequeas de elementos sino particularmente debido a su facilidad de programacin.
ImplementacinA continuacin se muestra el Ordenamiento por insercin en distintos lenguajes de programacin:Cvoid insertionSort(int numbers[], int array_size) { int i, a, index; for (i=1; i < array_size; i++) { index = numbers[i]; for (a=i-1;a >= 0 && numbers[a] > index;a--) { numbers[a + 1] = numbers[a]; } numbers[a+1] = index; } }
C++template void insertionSort(std::vector& v, int fin) { int i, j, index; for (i=1; i = 0 && v.at(j)>index) { v.at(j+1)=v.at(j); j--; } v.erase(v.begin()+j+1); v.insert(v.begin()+j+1,index); } }
Javapublic static void insertSort (int[] v) { int aux; int j; for (int i=1; i=0 && v[j]>aux; j--){ v[j+1] = v[j]; v[j] = aux; } } }
JavaScriptfor (var i=1; i < vector.length; i++) { var temp = vector[i]; var j = i-1; while (j >= 0 && vector[j] > temp) { vector[j + 1] = vector[j]; j--; } vector[j+1] = temp; }
Perl#!/usr/bin/perl use v5.12; my @array = qw( 1749472308 ); insercion(\@array); say "@array"; sub insercion { my $array_ref = shift; for my $i (1 .. $#$array_ref) { my $j = $i - 1; my $x = $array_ref->[$i]; next if $array_ref->[$j] = 0 and $array_ref->[$j] > $x); splice @$array_ref, $j+1, 0, splice @$array_ref, $i, 1; # extraccin e insercin! } }
__END__ 0123447789
PHPfunction insert_sort($arr){ $count = count($arr); for($i=1; $i=0 && $arr[$j] > $tmp; $j--) $arr[$j+1] = $arr[$j]; $arr[$j+1] = $tmp; } return $arr; }
PascalProcedure InsertionSort(var insertion:Array_integer; array_size: Integer); Var i, j, index : Integer; Begin For i := 1 to array_size do Begin index := insertion[i]; j := i-1; While ((j >= 0) AND (insertion[j] > index)) do Begin insertion[j+1] := insertion[j]; j := j - 1; End; insertion[j+1] := index; End; End;
Pythondef insertionSort(numeros): #numeros es una lista tama = len(numeros) #creamos una variable igual al tamao de la lista for i in range(tama): indice = numeros[i] a = i-1 while (a >= 0 and numeros[a] > indice): numeros[a+1] = numeros[a] a = a-1 numeros[a+1] = indice print (numeros) #imprime la lista ordenada
Rubydef insertion_sort(array) for j in 1...array.size key = array[j] i=j-1 while i >= 0 and array[i] > key
71
array[i + 1] = array[i] i=i-1 end array[i + 1] = key end array end
Visual Basic .NETPrivate Sub insertionSort(ByVal numbers() As Integer) ' Es una funcin, 'debemos pasarle el array de nmeros desde el Sub Main() Dim i, j, index As Integer i=1 Do index = numbers(i) j=i-1 While ((j >= 0) And (numbers(j) > index)) numbers(j + 1) = numbers(j) j=j-1 End While numbers(j + 1) = index i=i+1 Loop Until i > (UBound(v)) End Sub
C#class Program { public static void Main(string[] args) { int x=0; do{ Leer leer=new Leer(); leer.dato(); Console.WriteLine("Repitiendo..."); }while(x==0); Console.ReadKey(true); } } public class Inserccion_Directa { private static int temporal, posicion=0; static int[] x=new int[15]; public int ordenar(int entrada){ x[posicion]=entrada; posicion++; for(int y=1;y=0 && x[z]>temporal; z--){ x[z+1] = x[z]; x[z] = temporal; } } for(int m=0;m v[c]) min = c; } T aux = v[i]; v[i] = v[min]; v[min] = aux; } }
Perl# Recibimos una referencia a un array
sub seleccion { my $array = shift; my $i; my $j;
# ndice del elemento a comparar # ndice del valor mnimo a encontrar
# Para todos los elementos menos el ltimo for ( $i = 0; $i < $#$array; $i++ ) { # ndice y valor del elemento a comparar my ( $m, $x ) = ( $i, $array->[ $m ] ); # Buscamos el valor ms pequeo de todos los dems for ( $j = $i + 1; $j < @$array; $j++ ) { ( $m, $x ) = ( $j, $array->[ $j ] ) # Nuevo mnimo encontrado if $array->[ $j ] < $x; } # Hacemos el intercambio de elementos, si es necesario @$array[ $m, $i ] = @$array[ $i, $m ] if $m != $i; } }
JavaScript
for(var i=0 ; i 1 5033 > 0 Mientras mas grande sea nmero de elementos es mejor escoger un nmero primo mayor para seccionar el arreglo en ms partes. El nmero elegido da el nmero de partes en que se secciona el arreglo, y las cada seccin esta compuesta por todos los elementos que arrojen el mismo residuo, y mientras mas pequeas sean las secciones la bsqueda se agilizara mas que es lo que nos interesa. 3.- Mitad del cuadrado: Consiste en elevar al cuadrado la clave y coger las cifras centrales. Este mtodo tambin presenta problemas de colisin. 709^2=502681 > 26 456^2=207936 > 79 105^2=11025 > 1079
879^2=772641 > 26 619^2=383161 > 31 Nota: en caso de que la cifra resultante sea impar se toma el valor nmero y el anterior. 4.- Truncamiento: Consiste en ignorar parte del nmero y utilizar los elementos restantes como ndice. Tambin se produce colisin. Por ejemplo, si un nmero de 7 cifras se debe ordenar en un arreglo de elementos, se pueden tomar el segundo, el cuarto y el sexto para formar un nuevo nmero: 5700931 > 703 3498610 > 481 0056241 > 064 9134720 > 142 5174829 > 142 5.- Plegamiento: Consiste en dividir el nmero en diferentes partes, y operar con ellas (normalmente con suma o multiplicacin). Tambin se produce colisin. Por ejemplo, si dividimos el nmero de 7 cifras en 2, 2 y 3 cifras y se suman, dar otro nmero de tres cifras (y si no, se toman las tres ltimas cifras): 5700931 > 57 + 00 + 931 = 988 3498610 > 34 + 98 + 610 = 742 0056241 > 00 + 56 + 241 = 297 9134720 > 91 + 34 + 720 = 845 5174929 > 51 + 74 + 929 = 1054 Nota: Estas solo son sugerencias y que con cada problema se pude implementar una nueva funcin hash que incluso tu puedes inventar o formular. Tratamiento de colisiones Hay diferentes maneras de solucionarlas pero lo ms efectivo es en vez de crear un arreglo de nmero, crear un arreglo de punteros, donde cada puntero seala el principio de una lista enlazada. As, cada elemento que llega a un determinado ndice se pone en el ltimo lugar de la lista de ese ndice. El tiempo de bsqueda se reduce considerablemente, y no hace falta poner restricciones al tamao del arreglo, ya que se pueden aadir nodos dinmicamente a la lista. PRUEBA LINEAL Consiste en que una vez detectada la colisin se debe recorrer el arreglo secuencialmente a partir del punto de colisin, buscando al elemento. El proceso de bsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una posicin vaca. Se trata al arreglo como a una estructura circular: el siguiente elemento despus del ltimo es el primero. La funcin de rehashing es, por tanto, de la forma: R(H(X)) = (H(X) + 1) % m (siendo m el tamao del arreglo) Ejemplo: Si la posicin 397 ya estaba ocupada, el registro con clave 0596397 es colocado en la posicin 398, la cual se encuentra disponible. Una vez que el registro ha sido insertado en esta posicin, otro80
registro que genere la posicin 397 o la 398 es insertado en la posicin siguiente disponible. Ejemplo: Tomando en cuenta los datos de la seccin 2 de este tema crea un programa que mediante bsqueda hash encuentre los datos requeridos y asegurate de tratar las colisiones.using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.IO; namespace WindowsApplication1 { public partial class Form1 : Form { private int[] datos = new int[5] {1679, 4567, 8471, 0435, 5033 }; private int[] hash = new int[7]; private int[] enlace = new int[7]; public Form1() { InitializeComponent(); for (int b = 0; b
