Á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 comments:
Publicar un comentario