estructuradedatosfimeuanl

Estructuras Dinámicas no Lineales

Son aquellas que ocupan bloques de memoria no continuos / lineales. Para lidiar con el problema de la fragmentación y, sobretodo del crecimiento dinámico. Los bloques deben estar enlazados unos con otros para poder “navegar” por la estructura, es decir, tener acceso a otro(s) dato(s) a partir del actual.

Es una estructura donde se tienen relaciones no lineales y no secuenciales, se pueden encontrar colecciones no ordenadas de elementos del mismo tipo, donde no hay repeticiones.

A las estructuras de datos no lineales se les llama también estructuras de datos multienlazadas.

Características

· Se caracteriza por no existir una relación de sus elementos, es decir, que un elemento puede estar con cero, uno o más elementos.

· Las estructuras no lineales de datos más generales son los árboles donde no existe ninguna relación de orden predefinida.

Cada elemento puede estar enlazado a cualquier otro componente.

Tipos

Ø Arboles

Ø Gafos

Ø Tablas hash o de dispersión

Aplicaciones

Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos.

Se trata de estructuras de datos en las que cada elemento puede tener varios sucesores y/o varios predecesores.

Ventajas

ü Se requiere utilizar direcciones de memoria / apuntadores.

ü Se usan para lidiar con el problema de la fragmentación y, sobretodo del crecimiento dinámico.

Desventajas

û Necesitan apuntadores, de lo contrario no funciona.

û ocupan bloques de memoria solo no continuos / lineales.

Arboles

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto.

Formalmente, podemos definir un árbol de la siguiente forma:

· Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

Un nuevo árbol a partir de un nodo

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un árbol recorrido. Existen dos recorridos típicos para listar los nodos de un árbol: en profundidad y en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n+1 (a distancia n+1 aristas de la raíz), se deben haber listado todos los de nivel . Otros recorridos típicos del árbol son preorden, postorden e inorden:

· El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.

· El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

· El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar , luego la raíz y luego cada uno de los hijos en orden simétrico.

Componentes

Ø Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo 2, 'L' y 'M' son hijos de 'G'.

Ø Nodos Hermanos: Nodos que comparten el mismo padre.

Ø Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo 2, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.

En cuanto a la posición dentro del árbol:

Ø Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Ø Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Ø Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo. Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

v
Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

v Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.

v Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.

v Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Operaciones

Las operaciones comunes en árboles son:

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

Ø Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.

Ø Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

Salvo que trabajemos con árboles especiales, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles. De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:

ü Añadir o insertar elementos.

ü Buscar o localizar elementos.

ü Borrar elementos.

ü Moverse a través del árbol.

ü Recorrer el árbol completo.

Aplicaciones

Topología arbórea

Es una caracterización física de un objeto y sus componentes, que por su configuración se asemeja o recuerda a un árbol, en el sentido que sus ramificaciones tienden a converger en un origen o raíz (por ejemplo el llamado árbol genealógico).

Con este concepto se introduce por lo tanto las nociones de raíz y de descendencia.

Teoría de grafos

Es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.

Partición binaria del espacio

Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos del árbol conocida como árbol de BSP.

Hash Árboles

Se usa en los programas p2p y especializado imagen de la firma en la que un hash debe ser verificado, pero todo el archivo no está disponible.

Monticulo (Heap)

Estructura de datos del tipo árbol con información perteneciente a un conjunto ordenado. Los montículos máximos tienen la característica de que cada nodo padre tiene un valor mayor que el de cualquiera de sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.

La Codificación Huffman Árbol (Chip Uni)

Que se utiliza en los algoritmos de compresión, tales como los utilizados por él .jpeg y .mp3 archivo-formatos.

GGM Árboles

Que se Utiliza en aplicaciones criptográficas para generar un árbol de números pseudo-aleatorios.

El Árbol sintáctico

Construido por los compiladores y (implícitamente) calculadoras para analizar expresiones.

Treap

Aleatorios estructura de datos utilizados en las redes inalámbricas y la asignación de memoria.

T-árbol

Aunque la mayoría de las bases de datos de uso de alguna forma de árbol B para almacenar datos en el disco, las bases de datos que mantienen a todos (la mayoría) de sus datos en la memoria suele utilizar T-árboles para hacerlo.

Grafos

Estructura formada por un conjunto de nodos o vértices y un conjunto de aristas o lados. A ser usados por cualquier problema donde se observa un conjunto de objetos y conexiones entre ellos: mapa de rutas de transporte, red de computadoras, organigrama, diagrama de actividades/prelaciones, etc.

Los grafos son importantes ya que son un caso especial de árboles y es lo principal que estudia la teoría de grafos.

Componentes

v Aristas o arcos: son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

v Cruces: son dos aristas que cruzan en un punto

v Vértice: Son los puntos o nodos con los que está conformado un grafo.

v Lazos: es una arista cuyos extremos inciden sobre el mismo vértice

v Valencia de un vértice: Es el número de lados que salen o entran a un vértice.

Operaciones

En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.

Insertar vértice

La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ningúna arista llegará a él.

Insertar arista

Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.

Eliminar vértice

Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.

Eliminar arista

Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

Otras operaciones

Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.

Aplicaciones

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería.

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

Tablas Hash (o Dispersión)

Son estructuras de datos que se utilizan para almacenar un número elevado de datos sobre los que se necesitan operaciones de búsqueda e inserción muy eficientes. Una tabla hash almacena un conjunto de pares “(clave, valor)”. La clave es única para cada elemento de la tabla y es el dato que se utiliza para buscar un determinado valor.

Un diccionario es un ejemplo de estructura que se puede implementar mediante una tabla hash. Para cada par, la clave es la palabra a buscar, y el valor contiene su significado. El uso de esta estructura de datos es tan común en el desarrollo de aplicaciones que algunos lenguajes las incluyen como tipos básicos.

Un ejemplo práctico para ilustrar que es una tabla hash es el siguiente:

Se necesita organizar los periódicos que llegan diariamente de tal forma que se puedan ubicar de forma rápida, entonces se hace de la siguiente forma - se hace una gran caja para guardar todos los periódicos (una tabla), y se divide en 31 contenedores (ahora es una "hash table" o tabla fragmentada), y la clave para guardar los periódicos es el día de publicación (índice). Cuando se requiere buscar un periódico se busca por el día que fue publicado y así se sabe en qué zócalo (bucket) está. Varios periódicos quedarán guardados en el mismo zócalo (es decir colisionan al ser almacenados), lo que implica buscar en la sub-lista que se guarda en cada zócalo. De esta forma se reduce el tamaño de las búsquedas de O(n) a, en el mejor de los casos, O(1) y, en el peor, a O(log(n)).

Componentes

Las entradas de las tablas hash están compuestas por dos componentes:

Ø La propia clave.

Ø La información que se almacena en dicha entrada.

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.

Funcionamiento

Para usar una tabla hash se necesita:

ü Una estructura de acceso directo (normalmente un array).

ü Una estructura de datos con una clave

ü Una función resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales.

Las operaciones básicas implementadas en las tablas hash son:

v inserción (llave, valor).

1. Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen (hash) a la clave del elemento.

2. El resultado de la función resumen ha de mapearse al espacio de direcciones del vector que se emplea como soporte, lo cual se consigue con la función módulo. Tras este paso se obtiene un índice válido para la tabla.

3. El elemento se almacena en la posición de la tabla obtenida en el paso anterior.

3.1. Si en la posición de la tabla ya había otro elemento, se ha producido una colisión. Este problema se puede solucionar asociando una lista a cada posición de la tabla, aplicando otra función o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos.

v búsqueda (llave) que devuelve el valor.

1.
Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen (función computable mediante un algoritmo, que tiene como entrada un conjunto de elementos, y los convierte [mapea] en un rango de salida finito).

2. El valor obtenido se mapea al espacio de direcciones de la tabla.

3. Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

Una buena función hash es esencial para el buen rendimiento de una tabla hash. Las colisiones son generalmente resueltas por algún tipo de búsqueda lineal, así que si la función tiende a generar valores similares, las búsquedas resultantes se vuelven lentas.

En una función hash ideal, el cambio de un simple bit en la llave (incluyendo el hacer la llave más larga o más corta) debería cambiar la mitad de los bits del hash, y este cambio debería ser independiente de los cambios provocados por otros bits de la llave. Como una función hash puede ser difícil de diseñar, o computacionalmente cara de ejecución, se han invertido muchos esfuerzos en el desarrollo de estrategias para la resolución de colisiones que mitiguen el mal rendimiento del hasheo. Sin embargo, ninguna de estas estrategias es tan efectiva como el desarrollo de una buena función hash de principio.

Es deseable utilizar la misma función hash para arrays de cualquier tamaño concebible. Para esto, el índice de su ubicación en el array de la tabla hash se calcula generalmente en dos pasos:

1. Un valor hash genérico es calculado, llenando un entero natural de máquina.

2. Este valor es reducido a un índice válido en el vector encontrando su módulo con respecto al tamaño del array.

Funciones Hash más usadas:

1. Hash de División:

Dado un diccionario D, se fija un número m >= |D| (m mayor o igual al tamaño del diccionario) y que sea primo no cercano a potencia de 2 o de 10. Siendo k la clave a buscar y h(k) la función hash, se tiene h(k)=k%m (Resto de la división k/m).

2. Hash de Multiplicación:

Si por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, será mejor usar una función hash de multiplicación, independiente del tamaño de la tabla. Se escoge un tamaño de tabla m >= |D| (m mayor o igual al tamaño del diccionario) y un cierto número irracional φ (normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*φ)).

Ventajas de uso de tablas hash

Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy rápido si se cumplen las siguientes condiciones:

ü Una razón de ocupación no muy elevada (a partir del 75% de ocupación se producen demasiadas colisiones y la tabla se vuelve ineficiente).

ü Una función resumen que distribuya uniformemente las claves. Si la función está mal diseñada, se producirán muchas colisiones.

Desventajas

û Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operación costosa.

û Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos.

û Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume más memoria de la necesaria; se suele resolver reservando espacio únicamente para punteros a los elementos.

Aplicaciones

Ø La principal aplicación que se da a las Tablas Hash es la de confección de diccionarios, pues la facilidad de búsqueda hace que las palabras puedan ser encontradas en lapsos muy cortos. Por ejemplo, véase la siguiente estructura de clase para una palabra de un diccionario (definida en lenguaje Java):

public class TPalabra

{

private String palabra;

private String significado;

private String sinonimos[ ];

// métodos públicos

}

Parte de una clase TPalabra en lenguaje de programación Java.

En la misma se muestra la palabra a buscar, el significado de la misma y una lista de sinónimos que pueden ser utilizados como vínculos a otras palabras. El uso de una Tabla Hash para el diccionario almacenaría en un arreglo decenas de miles de objetos de tipo TPalabra, cada uno representando una palabra diferente. El usuario que desea buscar una palabra la escribe y pide su búsqueda. La propia palabra, por supuesto, es utilizada como clave para que la función Hash la localice dentro del arreglo. Al final son devueltas al usuario la descripción de la palabra y la lista de sinónimos.

Ø De la misma forma se pueden utilizar las Tablas Hash en los compiladores, para la búsqueda rápida de aquellos identificadores declarados y que han pasado a secciones de la memoria que no son directos. Algunas calculadoras científicas también poseen Tablas Hash que almacenan complejas operaciones que pueden ser llamadas luego de forma muy rápida.

Conclusiones

En este trabajo definimos que son las estructuras dinámicas no lineales y los tipos de cada una de ellas y descubrimos que son una buena alternativa cuando tienes información desordenada ya que las lineales no pueden manejar dicha información, entre ellas están los árboles, grafos y tablas hash.

Los árboles son estructuras dinámicas no lineales ya que cada nodo puede apuntar a uno o varios nodos, donde se puede decir que un árbol tiene un subárbol si tiene más de 2 niveles, y definimos sus componentes para ver que se puede hacer con cada uno de ellos, así como las aplicaciones.

Los grafos son importantes ya que son un caso especial de árboles, y en el definimos que es un grafo, los componentes que los conforman, las operaciones que realiza y sus aplicaciones, y que es importante ya que es el tema principal que estudia la teoría de datos.

Y por último el tema de tablas hash o de dispersión podemos concluir que de alguna forma son un tipo peculiar de estructuras dinámicas porque son estructuras de que se utilizan para almacenar datos, esta almacena un conjunto de datos, la clave es única para cada elemento de la tabla y es el dato que se utiliza para buscar un determinado valor.

Un tema muy interesante ya que conocimos lo que es una estructura dinámica no lineal, y sus tipos peculiares de componentes, y analizamos cada uno de sus componentes, un trabajo interesante.

DESCARGAR LA PRESENTACION EN POWER POINT