B2T3 Estructuras de datos.pdf

2015-2016 Bloque 2 - Tema 3 TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS. ORGANIZACIONES DE FICHEROS. ALGORITMOS. FORMATOS DE INFORMACIÓN Y FICHEROS PREPARACIÓN OPOSICIONES TÉCNICOS AUXILIARES DE INFORMÁTICA B2T3 ESTRUCTURAS DE DATOS...

2015-2016 Bloque 2 - Tema 3 TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS. ORGANIZACIONES DE FICHEROS. ALGORITMOS. FORMATOS DE INFORMACIÓN Y FICHEROS PREPARACIÓN OPOSICIONES TÉCNICOS AUXILIARES DE INFORMÁTICA B2T3 ESTRUCTURAS DE DATOS TAI ÍNDICE ÍNDICE............................................................................................................................................................ 2 1. TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS........................................................................................ 3 1. Arrays................................................................................................................................................... 5 2. Registros............................................................................................................................................... 7 3. Listas..................................................................................................................................................... 8 4. Pilas.................................................................................................................................................... 12 5. Colas................................................................................................................................................... 14 6. Tabla hash.......................................................................................................................................... 15 7. Conjuntos............................................................................................................................................ 16 8. Árboles................................................................................................................................................ 16 9. Grafos................................................................................................................................................. 24 2. ALGORITMOS.......................................................................................................................................... 29 1. Eficiencia de un algoritmo.................................................................................................................. 29 2. Recursividad....................................................................................................................................... 33 3. Algoritmos de búsqueda..................................................................................................................... 35 4. Algoritmos de ordenación o clasificación........................................................................................... 37 5. Algoritmos teoría de grafos................................................................................................................ 42 3. ORGANIZACIONES DE FICHEROS............................................................................................................. 43 1. Organización secuencial..................................................................................................................... 43 2. Organización directa.......................................................................................................................... 44 3. Variantes de la organización secuencial............................................................................................. 46 4. FORMATOS DE INFORMACIÓN Y FICHEROS............................................................................................ 51 1. Formatos de imágenes....................................................................................................................... 51 2. Formatos de documentos................................................................................................................... 53 3. Formatos de intercambio de datos..................................................................................................... 54 4. Formatos de audio y video................................................................................................................. 57 PABLO ARELLANO www.theglobeformacion.com Página 2 B2T3 ESTRUCTURAS DE DATOS TAI 1. TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS Para empezar, hay que precisar la diferencia entre tres conceptos muy relacionados, pero formalmente distintos, aunque sea frecuente utilizar el mismo nombre para casos concretos y muy importantes. Se trata de los conceptos de “Tipo de Datos”, “Tipo abstracto de Datos” y “Estructura de Datos”. Las definiciones se pueden establecer de la siguiente forma: Un Tipo de Datos (TD) es el conjunto de valores que puede tomar una variable. Los datos se pueden clasificar en dos tipos: - Dato elemental. Aquellos que pueden ser almacenados en cualquier soporte de información sin necesidad de ninguna estructura especial para su almacenamiento. Los datos elementales se pueden clasificar en tres grupos: a) Numéricos. Lo componen los guarismos (0, 1, 2, 3,..., 9), se utilizan para representación de información de tipo numérico. b) Alfabéticos: compuestos por los caracteres del alfabeto (a, b, c,..., x, y, z), se utilizan para representar información no numérica. c) Especiales: utilizados con fines sintácticos en la mayoría de los casos o con fines aritméticos en otros. Formados por todos los caracteres que no constituyen información por sí solos (¿, ?, =, ), (, /, &, %, etc.). - Tipos compuestos. Los más frecuentes son los arrays, listas, árboles, grafos, registros y ficheros. Los tipos de datos constituyen un primer nivel de abstracción, ya que no se tiene en cuenta cómo se implementan o se representa realmente la información sobre la memoria de la máquina. Para el usuario, el proceso de implementación o representación es invisible. Un Tipo Abstracto de Datos (TAD) representa una abstracción donde se destacan los detalles de la especificación (el qué) y se ocultan los detalles de la implementación (el cómo). Así un TAD es representado por su interfaz la cual muestra las operaciones que se pueden realizar sobre ese tipo de datos sin importar la implementación concreta. Así podemos definir un TDA Lista, un TDA Arbol, un TDA Pila o un TDA Cola, independientemente de las estructuras de datos usadas para su implementación. PABLO ARELLANO www.theglobeformacion.com Página 3 B2T3 ESTRUCTURAS DE DATOS TAI Una Estructura de Datos (ED) es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente, es decir, es la representación o implementación de un TAD. Clasificación de estructuras de datos 1ª CLASIFICACIÓN: según cómo se ubiquen en la memoria del ordenador - Contiguas: son aquellas que al representarse en el hardware del ordenador, lo hacen situando sus datos en áreas adyacentes de memoria. Ejemplos: cadenas, arrays, vectores, registros. - Enlazadas: sus datos no tienen por qué situarse de forma contigua en la memoria, en las estructuras enlazadas los datos se relacionan unos con otros mediante punteros. La localización del dato no es inmediata, sino que se produce a través de los punteros que relacionan unos datos con otros. 2ª CLASIFICACIÓN: Según la variabilidad de su tamaño durante la ejecución de un programa: - Estáticas: son aquellas en las que el tamaño ocupado en memoria se define con anterioridad a la ejecución del programa que las usa (en tiempo de compilación), y su dimensión no puede modificarse durante el proceso. Ejemplo: array o matriz. - Dinámicas: las estructuras de los datos pueden crecer o no en tamaño, durante la ejecución, dependiendo de las necesidades de la aplicación. Ejemplo: lista o árbol. Ventajas e inconvenientes de las agrupaciones estáticas frente a las agrupaciones dinámicas: - En agrupaciones estáticas es más fácil y rápido realizar búsquedas en vectores. - En general, para un mismo número de elementos las agrupaciones dinámicas ocuparán más memoria que las estáticas (por cada elemento se tiene también un puntero en las agrupaciones dinámicas). - En agrupaciones dinámicas es mayor la facilidad para insertar y eliminar elementos. - Es preferible las agrupaciones dinámicas si el número de elementos va a ser cualquiera. 3ª CLASIFICACIÓN: Según los tipos de datos de contengan: - Homogéneas: son aquellas en las que únicamente se utiliza un tipo de datos. - Heterogéneas: las estructuras que permiten que sus elementos puedan ser de tipos de datos distintos. PABLO ARELLANO www.theglobeformacion.com Página 4 B2T3 ESTRUCTURAS DE DATOS TAI boolean char Simples integer real ESTÁTICAS Strings Arrays Compuestas Conjuntos Estructuras Registros de datos Arrays Listas Lineales Pilas DINÁMICAS Colas Árboles No lineales Grafos 1. Arrays Colección de elementos homogéneos (de igual longitud y tipo) entre los que existe una relación lineal determinada por la posición del elemento dentro de la estructura, también se las conoce con el nombre de Array. Los arrays son estructuras de datos complejas que se caracterizan porque sus unidades homogéneas de información se ubican en posiciones contiguas de memoria. Los arrays dependiendo del lenguaje de programación pueden ser estáticos (de tamaño fijo determinado en tiempo de compilación) y dinámicos (el tamaño puede variar en tiempo de ejecución). Un array viene definido por: - La definición de sus elementos. Longitud y tipo de dato a almacenar en la estructura. - Índice (o varios). Es una variable numérica entera positiva que permite el acceso a los distintos elementos de la estructura según el valor de éste y, por tanto, según la posición PABLO ARELLANO www.theglobeformacion.com Página 5 B2T3 ESTRUCTURAS DE DATOS TAI en la que se encuentra el elemento dentro de la estructura. Un índice comienza en 0 y termina en tamaño-1. Podemos distinguir varios tipos de arrays: - VECTORES o arrays unidimensionales. - MATRICES o arrays bidimensionales: los elementos quedan estructurados en filas y columnas para su representación gráfica. Para acceder a cada elemento lo haremos con dos índices i para las filas y j para las columnas. PABLO ARELLANO www.theglobeformacion.com Página 6 B2T3 ESTRUCTURAS DE DATOS TAI - ARRAYS MULTIDIMENSIONALES. Respecto a la implementación del array se establece el número de elementos que forman la estructura, que siempre habrá que fijarlo, de alguna de las siguientes maneras: - Memoria estática (en tiempo de compilación): una vez que el programa ha sido preparado para ser ejecutado (compilado y enlazado), la posición y el espacio de memoria que utilizará el array en la ejecución del programa ya está fijado y no puede de ninguna forma cambiarse, hablamos de array estático. - Memoria dinámica (en tiempo de ejecución): diremos que el array es dinámico, pues el espacio en memoria no es de tamaño fijo, pudiendo el espacio de memoria variar en tiempo de ejecución. Las operaciones básicas que se realizan sobre un array son: crear el array, insertar/modificar/eliminar elementos, buscar un elemento concreto, ordenar los elementos del array y contar los elementos que contiene. La estrategia utilizada para la búsqueda y ordenación de elementos de un vector se verá en un apartado posterior. 2. Registros Las estructuras o registros son agrupaciones heterogéneas, contiguas y estáticas. Los elementos contenidos en la agrupación pueden ser de distintos tipos y se denominan campos, y suelen estar relacionados con la información referente a un objeto concreto. PABLO ARELLANO www.theglobeformacion.com Página 7 B2T3 ESTRUCTURAS DE DATOS TAI Ejemplos: Una persona (Nombre, edad, DNI…) Un libro (Título, autor, precio, disponible/agotado...) Los registros o estructuras definen nuevos tipos de datos que podemos utilizar a lo largo de nuestro programa. Es decir, una vez declarada la estructura podemos utilizar y declarar variables de ese nuevo tipo (de la misma forma que si declarásemos variables de tipo entero o real). La manera de acceder a cada uno de los campos es mediante el operador de acceso ‘.’. Ejemplo: //Definición registro struct Nombre { Tipo1 Campo1; Tipo2 Campo2;... }; //Declaración variable NombreVar : Nombre //Asignación NombreVar.Campo1 = valor; Los registros tienen como característica el anidamiento de estructuras. Las estructuras se pueden anidar, es decir, uno de los campos de una estructura puede ser a su vez otra estructura. 3. Listas Una lista es un TAD que se define como un conjunto lógico de elementos homogéneos (nodos) entre los que existe una relación lineal, considerados a cada uno de éstos como unidad básica de información dentro de la estructura. Cada elemento de la estructura puede estar formado por uno o varios campos. Nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. Es posible utilizar una estructura estática aunque no es lo habitual. Lista = colección de elementos homogéneos entre los que existe una relación lineal: - Cada elemento de la lista, a excepción del primero, tiene un único predecesor. - Cada elemento de la lista, a excepción del último, tiene un único sucesor. PABLO ARELLANO www.theglobeformacion.com Página 8 B2T3 ESTRUCTURAS DE DATOS TAI Una lista es una estructura de datos que cumple: - Todos sus componentes son del mismo tipo. - Cada elemento o nodo (datos+puntero) va seguido de otro del mismo tipo o de ninguno. - Sus componentes se almacenan según cierto orden. Las operaciones sobre una lista son: crear, insertar un elemento, buscar un elemento (si la lista es dinámica solo es posible la búsqueda secuencial) y eliminar un elemento. De entre estas operaciones la de mayor complejidad técnica es la de inserción, existiendo 3 casuísticas. Ejemplo: Partimos de la siguiente lista: Inserción de un elemento en mitad de la lista: Inserción de un elemento al principio de la lista: PABLO ARELLANO www.theglobeformacion.com Página 9 B2T3 ESTRUCTURAS DE DATOS TAI Inserción de un elemento al final de la lista: Tipos de listas según la forma de acceder al siguiente elemento: - Lista DENSA o CONTIGUA: la propia estructura determina cuál es el siguiente elemento de la lista (posición), los nodos son adyacentes en memoria. Por ejemplo, se puede usar una tabla para implementar una lista, de forma que el siguiente elemento de la lista fuera dado por el orden del índice (no confundir con el orden de los elementos del array). Nótese sin embargo que, puesto que un array es estático, la memoria reservada para implementar esta "lista" también será estática. - Lista ENLAZADA: cada elemento contiene la información necesaria para llegar al siguiente. Es una estructura dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. La posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además, como es dinámica, su tamaño cambia durante la ejecución del programa. Dentro de las listas enlazadas podemos distinguir, según la cantidad de enlaces por nodo, entre: o Lista simplemente enlazada: Cada elemento conoce que elemento es el que le sucede en el orden, pero no cual le precede. o Lista doblemente enlazada: Cada elemento conoce que elemento le precede y cual le sucede en el orden. Permite el recorrido de la lista en ambos sentidos. Sin embargo, como inconveniente ocupa más memoria que una lista simplemente enlazada. o Lista con enlaces múltiples: Son aquellas listas en donde cada elemento, aparte de conocer los elementos que le preceden o suceden, también tiene uno o varios enlaces al primer elemento de otra lista, siendo éstas sublistas de la anterior. PABLO ARELLANO www.theglobeformacion.com Página 10 B2T3 ESTRUCTURAS DE DATOS TAI o Skip list o lista por saltos: es una estructura de datos, basada en listas enlazadas paralelas con eficiencia comparable a la de un árbol binario. Es una lista ordenada (y en principio sin claves repetidas) en la que cada nodo puede tener uno o varios enlaces al nodo siguiente y a diversos nodos a distancias variables, bien establecidas de forma aleatoria o siguiendo un patrón establecido de saltos a longitudes fijas. - Lista ORDENADA: La posición de cada nodo viene determinada por el valor de uno o más campos obligatorios de información del nodo denominados clave. No se permite tener dos nodos con la misma clave. - Lista CIRCULAR: es una lista en la que el último nodo apunta al primero en lugar de ser null. Una lista circular se puede aplicar a listas simplemente enlazadas como a listas doblemente enlazadas. PABLO ARELLANO www.theglobeformacion.com Página 11 B2T3 ESTRUCTURAS DE DATOS TAI 4. Pilas Una pila se considera un caso particular lista. Es un TAD que se define como una colección de elementos homogéneos en la que sólo se pueden añadir y eliminar elementos por el principio de la misma (cabecera o tope), siguiendo la filosofía LIFO1 (Last In First Out). Un concepto a destacar es la cabecera o el tope que apunta a la posición en la que se insertan y eliminan los elementos de la pila. Las operaciones básicas para manipular una pila son: - Push o Apilar: añade un elemento en la posición siguiente al tope actual. - Pop o Desapilar: elimina el elemento situado en el tope. Aplicaciones prácticas de una pila: - Vuelta atrás en un navegador web. - Función Deshacer en un procesador de texto. - Invocación a métodos. 1 En la teoría de colas, encargada del estudio de las colas o las líneas de espera, los modelos de disciplina de cola se refieren se encarga de establecer el orden en el que sus miembros (elementos) se seleccionan para recibir el servicio. Destacan los siguientes modelos: - LIFO (Last In First Out): se atiende primero al miembro que ha llegado el último. - FIFO (First In First Out): se atiende primero al miembro que ha llegado antes. - RSS (Random Selection of Service): se atiende a los miembros de forma aleatoria. PABLO ARELLANO www.theglobeformacion.com Página 12 B2T3 ESTRUCTURAS DE DATOS TAI - Notación polaca inversa (RPN, Reverse Polish Notation): es otra forma de escribir expresiones matemáticas (lo normal, notación infija). Se usa en ciertas calculadoras. Por ejemplo, dada la expresión infija 10-(4+3)*2 (el resultado es -4), su equivalente en notación postfija (o postfix) es 10 4 3 + 2 * -. Forma de resolver: recorrer la expresión de izquierda a derecha, apilando los números (operandos). Cuando se encuentra un operador se desapilan los dos últimos operandos, se resuelve la operación y el resultado se apila de nuevo. Finalizada la expresión, en la pila solo debe quedar el resultado final. Vemos el ejemplo: 10 4 3 + 2 * - Se inserta 10 10 10 4 3 + 2 * - Se inserta el 4 4 10 10 4 3 + 2 * - 3 Se inserta el 3 4 10 PABLO ARELLANO www.theglobeformacion.com Página 13 B2T3 ESTRUCTURAS DE DATOS TAI 10 4 3 + 2 * - Se suman 3 y 4 y se apila el 7 resultado 10 10 4 3 + 2 * - 2 Se inserta el 2 7 10 10 4 3 + 2 * - Se multiplican 2 y 7 y se apila 14 el resultado 10 10 4 3 + 2 * - Se restan 14 y 10 y se apila el resultado -4 5. Colas Una cola también es considerada un caso especial de lista. Es un TAD que se define como una colección ordenada de elementos homogéneos en la que sólo se pueden añadir elementos por el final y se eliminan por el principio (frente), siguiendo la filosofía FIFO (First In First Out). Las operaciones básicas para manipular una cola son: - Queue o Encolar: añade un elemento al final de la cola. - Dequeue o Desencolar: elimina el primer elemento de la cola. PABLO ARELLANO www.theglobeformacion.com Página 14 B2T3 ESTRUCTURAS DE DATOS TAI Aplicaciones prácticas de una cola: - Listas de espera. - Acceso a recursos compartidos dedicados. - Multiprogramación de la CPU. 6. Tabla hash Una tabla Hash es un contenedor asociativo (tipo Diccionario) que permite un almacenamiento y posterior recuperación eficientes de elementos (denominados valores) a partir de otros objetos, llamados claves. Una tabla hash se puede ver como un conjunto de entradas. Cada una de estas entradas tiene asociada una clave única y, por lo tanto, diferentes entradas de una misma tabla tendrán diferentes claves. Esto implica, que una clave identifica unívocamente a una entrada en una tabla hash. Una tabla hash está formada por un array de entradas, que será la estructura que almacene la información, y por una función de dispersión. La función de dispersión permite asociar el elemento almacenado en una entrada con la clave de dicha entrada. Por lo tanto, es un algoritmo crítico para el buen funcionamiento de la estructura. Cuando se trabaja con tablas hash es frecuente que se produzcan colisiones. Las colisiones se producen cuando para dos elementos de información distintos, la función de dispersión les asigna la misma clave. Como se puede suponer, esta solución se debe arreglar de alguna forma. Para ello las tablas hash cuentan con una función de resolución de colisiones. Existen dos tipos de tablas hash, en función de cómo resuelven las colisiones: - Encadenamiento separado (hashing ABIERTO): las colisiones se resuelven insertándolas en una lista. De esa forma tendríamos como estructura un vector de listas. Al número medio de claves por lista se le llama factor de carga y habría que intentar que esté próximo a 1. PABLO ARELLANO www.theglobeformacion.com Página 15 B2T3 ESTRUCTURAS DE DATOS TAI - Direccionamiento abierto (hashing CERRADO): utilizamos un vector como representación y cuando se produzca una colisión la resolvemos reasignándole otro valor hash a la clave hasta que encontremos un hueco. 7. Conjuntos Es una colección homogénea y no ordenada de elementos distintos, entre los cuales existe una relación de orden. Se suele implementar mediante arrays. 8. Árboles Un árbol es una estructura de datos jerárquica no lineal, en la que existen relaciones padre- hijo entre nodos. Formalmente es un grafo no dirigido acíclico y conexo. Se caracterizan por estar formados por una serie de nodos conectados por una serie de aristas verificándose que: - Hay un único nodo raíz. - Cada nodo, excepto el nodo raíz, tiene un único padre. - Hay un único camino desde la raíz hasta cada nodo, es decir, no hay ciclos. Y como definiciones básicas tenemos que: - El nodo raíz es el único nodo sin padre. - Un nodo interno es aquel que tiene al menos un hijo. - Un nodo hoja es aquel nodo que no tiene descendientes. A partir del árbol del ejemplo se expondrán algunas definiciones: PABLO ARELLANO www.theglobeformacion.com Página 16 B2T3 ESTRUCTURAS DE DATOS TAI - El grado de un nodo es el número de hijos o descendientes directos. En el ejemplo, Grado(F)=3, Grado(B)=2 y Grado(A)=3. - El grado de un árbol es el mayor grado de sus nodos. En el ejemplo, Grado=3. - Un subárbol es el árbol formado por un nodo y todos sus descendientes. En el ejemplo el formado por {C, G, H}. - La profundidad de un nodo es la longitud del camino desde la raíz hasta ese nodo. En el ejemplo, Profundidad(J)=3, Profundidad(D)=1 y Profundidad(H)=2. - La altura del árbol es la profundidad máxima de cualquier nodo. En el ejemplo, Altura=3. - El nivel de un nodo se define como sigue: la raíz del árbol tiene nivel 1, el nivel de cualquier nodo es el nivel de su padre más uno. El nivel de un árbol vacío es cero. En el ejemplo, el árbol tiene 4 niveles, el nivel de A es 1 y el nivel de G es 3. - Un camino entre dos nodos X e Y existe si existe una sucesión de nodos que permitan llegar desde X a Y. En el ejemplo, Camino(A, K) = {A, B, F, K} y Camino(C, K) = {}. - Un árbol ponderado es aquel en el que cada arista tiene asociado un peso. Por último, el TAD Lista es un árbol degenerado de grado 1. Por otro lado, las operaciones básicas a realizar con los árboles son: crear un árbol, recorrer el árbol (en amplitud o en profundidad), insertar/eliminar un nodo, buscar un elemento, ordenar el árbol y contar número de nodos. Respecto a la implementación, los árboles pueden implementarse internamente mediante arrays o punteros. Lo más habitual es utilizar memoria dinámica, es decir, punteros. PABLO ARELLANO www.theglobeformacion.com Página 17 B2T3 ESTRUCTURAS DE DATOS TAI Clasificación de los árboles según el grado Según el grado del árbol podemos clasificar los árboles en: - Árboles BINARIOS: de grado = 2. o Árbol binario de búsqueda (ABB). o Árbol AVL: ABB equilibrado en altura. - Árboles MULTICAMINO: de grado > 2. o Árbol B. o Árbol B+. o Árbol B*. Árboles BINARIOS (AB) Un árbol binario es un árbol de grado 2, tiene un nodo raíz y se cumple que cada nodo tiene como máximo dos hijos: el hijo izquierdo y el hijo derecho. Se define un AB completo como un AB donde todo nodo interno tiene 2 descendientes directos. ¿Cómo recorrer los nodos de un árbol? Dos tipos de recorrido: en profundidad y en anchura. Recorrido en profundidad: dimensión vertical. Existen 3 modos: - Preorden (R-IZQ-DCHA): primero se visita el nodo raíz, luego el subárbol izquierdo y, por último, el subárbol derecho. - Inorden (IZQ-R-DCHA): primero se visita el subárbol izquierdo, luego el nodo raíz y, por último, el subárbol derecho. - Postorden (IZQ-DCHA-R): primero se visita el subárbol izquierdo, luego el subárbol derecho y, por último, el nodo raíz. Ejemplo: Recorrido en profundidad del árbol siguiente. Preorden: F, B, A, D, C, E, G, I, H. Inorden: A, B, C, D, E, F, G, H, I. Postorden: A, C, E, D, B, H, I, G, F PABLO ARELLANO www.theglobeformacion.com Página 18 B2T3 ESTRUCTURAS DE DATOS TAI Recorrido en anchura: dimensión horizontal. Se recorre el árbol por niveles y de izquierda a derecho. Ejemplo: Recorrido en anchura del árbol del ejemplo anterior. F, B, G, A, D, I, C, E, H Las aplicaciones prácticas de este tipo de estructura son diversas, pudiendo destacar las expresiones aritméticas y los árboles de decisión. Ejemplo: expresiones aritméticas. 2(a-1)+3b Ejemplo: árboles de decisión. El nodo interno contiene preguntas con respuesta Sí/No y los nodos hoja decisiones. La estructura de datos de un árbol binario es dinámica, donde cada nodo contiene un elemento, un puntero al nodo hijo izquierdo, un puntero al nodo hijo derecho y, quizá, un puntero al nodo padre. PABLO ARELLANO www.theglobeformacion.com Página 19 B2T3 ESTRUCTURAS DE DATOS TAI Árboles BINARIOS DE BÚSQUEDA (ABB) En este tipo de árboles cada nodo tiene asociado un valor clave y este valor de clave es mayor que los valores de clave de los nodos de su subárbol izquierdo y menor que todos los de su subárbol derecho. Claves Subárbol IZQUIERDO < Clave nodo RAÍZ < Claves Subárbol DERECHO Esto significa que para que un árbol binario sea ABB, se tiene que cumplir para cualquier nodo, que todos los valores del subárbol izquierdo del nodo son menores que el valor del nodo y que todos los valores del subárbol derecho. deben ser mayores que los valores del nodo. Ejemplo: ¿Cuál de los siguientes árboles es un ABB? Una de las ventajas de utilizar un ABB es que si se realiza un recorrido en Inorden por un ABB accederemos a los valores en orden ascendente. El proceso de búsqueda en un árbol binario de búsqueda se realiza recursivamente, desde la raíz hasta las hojas. Ejemplo: Recorrido Inorden de un ABB. PABLO ARELLANO www.theglobeformacion.com Página 20 B2T3 ESTRUCTURAS DE DATOS TAI Inorden (I-R-D) = 1,3,4,6,7,8,10,13,14 Un inconveniente de esta estructura es que puede llegar a degenerar en una lista, se soluciona equilibrando el ABB. Árboles AVL Un árbol AVL (Adelson-Velskii y Landis) es un ABB equilibrado en altura. La condición que debe satisfacer un árbol para que sea AVL es que para todo nodo la altura de sus subárboles izquierdo y derecho no difiere en más de una unidad. Gracias a que el árbol es equilibrado las búsquedas son más rápidas: O(log N). Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los árboles binarios de búsqueda (ABB), y además el dato que controla el factor de equilibrio. Se puede imponer una restricción mayor si se pretende que el árbol tenga un equilibrio perfecto. La condición consiste en que, para todo nodo del árbol, el número de nodos del subárbol izquierdo no difiere en más de una unidad del número de nodos del subárbol derecho. PABLO ARELLANO www.theglobeformacion.com Página 21 B2T3 ESTRUCTURAS DE DATOS TAI Árboles multicamino Son aquellos cuyo grado es mayor que 2. Se refiere el multicamino a que cada nodo tiene un número arbitrario de nodos. Una implementación típica es tener una lista de hijos por cada nodo. La implementación de los árboles multicamino se puede abordar de dos formas: - Diseñando los hijos como arrays de punteros: Desaprovecha la memoria si el número de hijos es muy variable a no ser que se diseñe de manera dinámica y no debería de usarse si el número de hijos es ilimitado. - Diseñando los hijos con punteros al hermano siguiente y a su hijo. A La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos. Por el contrario, el inconveniente más importante que tienen es la mayor ocupación de memoria, pudiendo ocurrir que en ocasiones la mayoría de los nodos no tengan descendientes o al menos no todos los que podrían tener desaprovechándose por tanto gran cantidad de memoria. PABLO ARELLANO www.theglobeformacion.com Página 22 B2T3 ESTRUCTURAS DE DATOS TAI Árboles B Son árboles multicamino, de un orden determinado que se caracteriza por: - Cada página tiene como máximo N nodos. - Cada página excepto la raíz tiene como mínimo N/2 nodos. - Cada página es o una página hoja o tiene m+1 descendientes (m es el número de nodos que contiene una página). Se define el orden de un árbol B como el número máximo de hijos de una página. La estructura de una página con m claves es: donde se cumple siempre que: ki < ki+1 ∀ i = 1... m N/2 < = m < = N ∀i =1... m, pi apunta a una página donde ki 0 / t1(n) ≤ ct2(n). Así, se podrá hacer que un programa vaya 10 ó 1.000 veces más rápido cambiando de máquina, pero sólo un cambio de algoritmo nos permitirá obtener una mejoría mayor cuanto más crezca el tamaño de la entrada, lo que nos llevará a ignorar las constantes multiplicativas a todos los efectos. Ahora bien, un mismo algoritmo puede ejecutarse con conjuntos de datos diferentes y su tiempo de ejecución puede ser distinto para cada uno de ellos: habrá datos de entrada con los que el algoritmo emplee más tiempo, y otros con los que finalice antes, por lo que es conveniente indicar si la expresión que se obtiene al realizar el análisis de la eficiencia corresponde: - Al caso peor: estamos indicando un límite superior, el máximo valor, del tiempo de ejecución para cualquier entrada al algoritmo. - Al caso promedio: será una media ponderada de ambos casos, aunque los abundantes y a veces complicados cálculos para realizar un análisis de eficiencia del caso promedio complican notablemente su uso. - Al mejor caso: donde ofrecemos un límite inferior, indicando que el algoritmo no se ejecutará por debajo de ese tiempo. Aunque el peor caso suele ser bastante pesimista, y probablemente el comportamiento del algoritmo sea algo mejor que el obtenido por el análisis, se suele utilizar más a menudo que el mejor. ¿Cómo se calcula el tiempo de ejecución de un algoritmo? Sobre la base de las instrucciones que componen el algoritmo. Aunque posteriormente lo estudiaremos con detalle, esbozaremos seguidamente algunas ideas. - La evaluación de una expresión tendrá como tiempo de ejecución lo que se tarde en realizar las operaciones que contenga. - Una asignación a una variable simple de una expresión, al igual que una operación de escritura de una expresión, suele tardar el tiempo de evaluar dicha expresión más un tiempo constante relativo a gestión interna de la asignación o del proceso de escritura. PABLO ARELLANO www.theglobeformacion.com Página 30 B2T3 ESTRUCTURAS DE DATOS TAI - Una lectura de una variable requiere un tiempo constante. - Una secuencia de instrucciones, la suma de los tiempos de cada una de las instrucciones. - En una sentencia condicional, su tiempo de ejecución será el de evaluar la condición más el máximo de los costes del bloque IF y del bloque ELSE. - Para un bucle, se evalúa el tiempo del cuerpo del bucle y se multiplica por el número de iteraciones más el tiempo de evaluar la condición del bucle. Todas aquellas instrucciones cuyo tiempo de ejecución queda limitado superiormente por una constante, que sólo depende de la implementación, se denominarán operaciones elementales. Por tanto, al habernos desprendido de las constantes multiplicativas, para el análisis de la eficiencia de un algoritmo sólo será relevante el número de operaciones primitivas y no su duración. Veamos un primer ejemplo para identificar intuitivamente estos conceptos. La siguiente función obtiene la posición donde se encuentra el mínimo valor de un vector de números enteros: int BuscarMinimo(int *Vector, int n) { int j, min; min= 0; for (j=1; j