No es un bug, es una característica no documentada

sábado, 14 de marzo de 2015

Programación. ADA. Tipos abstractos de datos (II)

17:56 Posted by Inazio , No comments

Árbol binario

·         Implementación estática. Un vector con componentes con cuatro campos (información, índice del hijo izquierdo – 0 si no hay hijo izquierdo -, índice del hijo derecho – lo mismo -, y si hay algo en esa componente o no. La raíz se almacena en la primera componente del vector.
·         Implementación dinámica. La que ya conocemos, nodos con información y dos punteros a los hijos.

Árbol n-ario

En general un árbol no tiene por qué tener sólo dos hijos como máximo. Hay problemas que pueden llevar a que un nodo pueda tener un número de hijos mayor, 3, 4, 5 o incluso puede ocurrir que no quede fijado a priori el número de hijos máximo que pueda tener un nodo.

Vamos a ver una posible representación estática para un árbol n-ario general, que sólo es razonable si el árbol es completo o caso completo. En este caso el valor de n puede ser cualquiera pero tiene que estar fijado a priori.

Vamos a ver una representación dinámica, que es lo más razonable que suele emplearse cuando se trabaja con árboles n-arios

·         Implementación estática.
Se utiliza un vector de 0 a máx-1 componentes para almacenar los elementos.
La raíz  se almacena en la componente 0.

Si un nodo es el hijo k-ésimo de padre en un árbol n-ario, será almacenado en la componente n*indice(padre)+k

El número de componentes necesario para almacenar un árbol n-ario arbitrario de altura h es


       Consideraciones para la implementación estática:
·         Conocido el índice que le corresponde a un elemento e en el vector, es fácil calcular el índice que le corresponde a su padre, hermanos e hijos:
·         Elemento, índice, condición
·         e, i
·         Hijo k-ésimo de e, n*i+k, si n*i+k<max
·         Padre de e, (i-1) div n, si n<>0
·         Hermano siguiente a e, i+1, si i mod n <> 0

·         Número de orden entre sus hermanos, ((i-1) mod n)+1, si i<>0


·         Implementación estática
Lo primero que se nos puede ocurrir es adaptar la que ya utilizamos para los árboles binarios: nodos con información y una lista de punteros a los hijos

Lo que se suele utilizar es precisamente eso mismo, pero “visto desde otra perspectiva”: la representación primogénito-siguiente-hermano.

Cada nodo tiene además de la información dos punteros, uno que apunta al primogénito (es decir, al primero de los hijos) y otro que apunta al siguiente hermano.

Árboles de búsqueda

Una de las más importantes aplicaciones que tienen los árboles es la de permitir realizar en ellos búsquedas con costes temporales logarítmicos (es decir, mucha mayor eficiencia que en estructuras lineales recorridas secuencialmente).

Para poder realizar búsquedas eficientes en árboles, logarítmicamente éstos deben estar ordenados.

Hay una gran variedad de tipos de árboles de búsqueda en función de su grado y restricciones.

Clasificación de árboles de búsqueda
·         Árboles binarios de búsqueda
·         Árboles AVL (binarios equilibrados)
·         Árboles m-arios de búsqueda (también llamados árboles de búsqueda múltiple o multicamino)
·         Árboles m-arios de búsqueda equilibrados
·         Árboles B de grado m
·         Árboles 2-3
·         Árboles B* de grado m
·         Árboles B+
·        

Árboles m-arios de búsqueda

Los nodos almacenan m-1 elementos ordenados de menor a mayor.

El subarbol 1 el nodo es menor que el menor de los elementos del nodo del que cuelga.
El subarbol 2, mayor que el primero y menor que el segundo, y así sucesivamente.

Ejemplo: Árbol 3-ario de búsqueda


Árboles B

Un árbol B de orden m tiene las siguientes propiedades
·         Es un árbol m-ario de búsqueda
·         La raíz es una hoja o tiene al menos dos hijos
·         Cada nodo, excepto la raíz y las hojas, tienen al menos m/2 hijos
·         Todas las hojas están en el mismo nivel

Un árbol 2-3 es un árbol B de orden 3. Cada nodo excepto las hojas, tiene dos o tres hijos.

Un árbol B* se caracteriza porque todos los nodos (excepto la raíz, y lógicamente las hojas), están por lo menos a 2/3 de ocupación en vez de a 1/2 , como el caso general de los árboles B.

Un árbol B+ es un árbol B que tiene todas las hojas enlazadas (formando una lista, para aumentar la eficiencia de ciertas operaciones). En un árbol B+ toda la información se guarda en las hojas y los nodos intermedios sólo guardan información de claves.

Grafos

Conceptos básicos

Un grado es una relación arbitraria entre objetos de un mismo tipo.

Puede definirse formando como un par G = (V,A) donde V es un conjunto de objetos llamados vértices o nodos y A es un conjunto de aristas o arcos. Una arista es un par (u,v) de vértices de V.

El grafo se llama dirigido, si sus aristas son pares ordenados. Es decir, si la aristas (u,v) se considera distinta a la arista (v,u). En caso contrario es no dirigido.

En muchas ocasiones es útil asociar información a cada arista de un grafo. En ese caso el grafo se dice etiquetado y se llama etiqueta de una arista a su información asociada. En ocasiones las etiquetas son valores numéricos que representan valores o costes asociados a las aristas, y se denominan pesos.

Por ejemplo, los vértices de un grafo no dirigido pueden representar ciudades con aeropuerto, las aristas servicios de vuelo de ida y vuelta entre las ciudades, y el peso asociado a cada arista, la duración del vuelo entre las dos ciudades correspondientes.

El grafo del ejemplo anterior podría ser dirigido si quisiésemos contemplar la posibilidad de que sólo hay vuelos en un sentido entre dos ciudades.

Caminos en grafos

Un camino en un grado G = (V,A) es una secuencia de vértices v1,…,vn tal que existen las aristas (vi, vi+1) para i = 1,…,n-1

La longitud de un camino es su número de vértices menos uno.

Un camino es simple si todos sus vértices, excepto tal vez el primero y el último, son distintos.

Un ciclo es un camino simple de longitud no nula que empieza y termina en el mismo vértice. Un grado es acíclico si no tiene ningún ciclo.

Los árboles son grafos

Un subgrafo de un grafo G es otro grafo G cuyos vértices y aristas son un subconjunto de los vértices y aristas de G.

Un grafo no dirigido se dice conexo si existe un camino entre cada par de vértices.

Un árbol libre es un grafo no dirigido, conexo y acíclico. Si en un árbol libre se destaca un vértice, denominado raíz, el grafo se denomina árbol.

Spanning tree

Un subárbol de recubrimiento de un grafo no dirigido (spanning tree) es un árbol libre que es subgrafo del grafo original y que incluye todos sus vértices.

En un grafo no dirigido y con pesos, el cálculo del árbol de recubrimiento de peso mínimo (árbol de recubrimiento cuya suma de pesos es mínima) es un problema de especial interés.

Si, por ejemplo, los vértices representan ciudades, las aristas las posibles líneas de comunicación entre ellas y el peso de una arista el coste de seleccionar esa línea de comunicación, un árbol de recubrimiento de peso mínimo representa una red de comunicaciones entre todas las ciudades que minimiza el coste.

Operaciones para grafos

è Crear grafo vacío
è Añadir vértice al grafo
è Añadir arista entre dos vértices
è Averiguar si existe el vértice en el grafo
è Averiguar si existe arista entre dos vértices en el grafo
è Averiguar con qué vértices existe comunicación directa desde un vértice
è

Implementación estática. Matriz de adyacencia

Si el grafo tiene n vértices, la matriz de adyacencia para el grafo es una matriz A de dimensiones nxn de elementos booleanos en la que A[i,j] es verdad, si y sólo si existe una arista en el grado que va del vértice i al vértice j.

En el caso de un grafo no dirigido, la matriz de adyacencia tiene la particularidad de ser simétrica y los elementos de su diagonal son todos igual a falso.

La representación de la matriz de adyacencia es útil para aquellos algoritmos que precisas saber si existe o no una arista entre dos vértices dados.

En el caso de grados etiquetados con pesos, los elementos de la matriz pueden ser enteros o reales (en lugar de booleanos) y representar el peso de la arista. Si no existe una arista de i a j debe emplearse un valor que no pueda ser una etiqueta válida para almacenarse en A[i,j].

Implementación dinámica. Lista de adyacencia

Consiste en una lista de listas, de forma que la lista i-ésima contiene los vértices adyacentes al vértice i.

En el caso de un grafo no dirigido, si tengo la arista (u,v), el vértice v estará en la lista de adyacencia de vértice u, y el vértice u lo estará a su vez en la del v.

Para representar un grafo etiquetado con pesos, basta con añadir otro campo al tipo nodo que almacene el peso correspondiente.

0 comentarios:

Publicar un comentario