estructura de datos - árboles y grafos

ESTRUCTURA DE

DATOS

Representación de

Árboles y Grafos

Miguel Angel Martínez Rodríguez

ÁRBOLES

Descripción:Es una estructura de datos no-lineal y dinámica que

almacena elementos.


¿POR QUÉ?

No-lineal:Puesto que a cada elemento del árbol le pueden seguir o no

varios elementos.

Dinámica:Puesto que la estructura del árbol puede cambiar durante la

ejecución del programa.

DEFINICIÓN

Es una estructura jerárquica aplicada sobre una colección de

elementos u objetos llamados nodos; uno de los cuales es

conocido como raíz y creando una referencia de parentesco.


REPRESENTACIÓN

DE GRÁFICAS

a) Diagrama de Venn

b) Anidación de paréntesis.

c) Notación decimal de Dewey.

REPRESENTACIÓN

DE GRÁFICAS

d) Notación Indentada

e) Grafos

CARACTERISTICAS

Árbol que no es vacío, tiene un único nodo raíz.

Un nodo X es hijo de Y, si es descendiente directo de este.

Un nodo X es padre de Y, si es antecesor directo de este.

Nodos hermanos, descendientes directos de un nodo padre.

Nodo terminal u hoja, aquel que no tiene ramificaciones.

Nodo interior, aquel que no es raíz, terminal u hoja.

CARACTERISTICAS

Grado, número de descendientes directos de un determinadonodo.

Grado del árbol, es el máximo grado de todos los nodos.

Nivel, número de arcos que deben ser recorridos para llegar aun determinado nodo.

Altura, máximo número de niveles del árbol.

LONGITUD DE

CAMINO INTERNO

Es la suma de las longitudes de camino de todos los

nodos del árbol.

FORMULA;

Donde;

i: representa el nivel del árbol.

h: representa la altura del árbol.

ni: representa el número de nodos en cada nivel.


MEDIA DE LA LONGITUD

DE CAMINO INTERNO

Se calcula dividiendo la LCI entre el número de

nodos del árbol.

FORMULA;

Donde;

n: representa el número total de nodos del árbol.


EJEMPLO

Determinar del siguiente árbol;

O Longitud del Camino Interno.

O Media de la Longitud de Camino Interno.

LCI= (1*1) + (2*2) + (2*3) + (2*4)

LCI= 1 + 4 + 6 + 8

LCI= 19

LCIM= 19/ 7

LCIM= 2.714


NODO ESPECIAL

Tienen como objetivo reemplazar las ramas vacías o nulas del

árbol, no pueden tener descendientes y normalmente se

representan con la forma de un “cuadrado”.

A continuación se presenta un árbol con nodos especiales:

Nodo Especial

Nodo Especial

CONCEPTO DE

ÁRBOL EXTENDIDO

Es aquel en el que el número de hijos de cada nodo es

igual al grado del árbol.

Si alguno de los nodos del árbol no cumple esta

condición entonces deben incorporarse al mismo nodos

especiales, tantos como sea necesario para satisfacer la

condición.

Es la suma de las longitudes de camino de todos los nodosespeciales del árbol.

FORMULA;

Donde;

i: representa el nivel del árbol.

h: representa la altura del árbol.

nei: representa el número de nodos especiales en el nivel i.

i comienza desde el nivel 2.

LONGITUD DE

CAMINO EXTERNO

MEDIA DE LA LONGITUD

DE CAMINO EXTERNO

Se calcula dividiendo la LCE entre el número de nodos

especiales del árbol.

FORMULA;

Donde;

ne: representa el número total de nodos especiales del

árbol.


EJEMPLO

Determinar del siguiente árbol;

O Longitud del Camino Externo.

O Media de la Longitud de Camino Externo.

LCE= (2*3) + (4*4)

LCE= 6 + 16

LCE= 22

LCEM= 22/ 6

LCEM= 3.666


ÁRBOLES BINARIOS

Son árboles ordenados de grado 2.

En un árbol binario cada nodo puede tener como

máximo dos subárboles y siempre es necesario distinguir

entre el subárbol izquierdo y el subárbol derecho.

ÁRBOLES BINARIOS

DISTINTOS

Son aquellos en los cuales, sus estructuras son diferentes.


ÁRBOLES BINARIOS

SIMILARES

Son aquellos en los cuales, sus estructuras son idénticas,

pero la información que contienen sus nodos difieren

entre sí.


ÁRBOLES BINARIOS

EQUIVALENTES

Se definen como aquellos que son similares y

además los nodos contienen la misma información.


ÁRBOLES BINARIOS

COMPLETOS

Árbol en el que todos sus nodos, excepto los del

ultimo nivel, tienen dos hijos: el subárbol izquierdo

y el subárbol derecho.


NODOS DE UN ÁRBOL

BINARIO COMPLETO

Se puede calcular el número de nodos de un árbol

binario completo de altura h.

FORMULA;

Donde;

ABC: significa Árbol Binario Completo.

h: es la altura del árbol.

NÚMERO DE

NODOSABC = (2^h)-1


EJEMPLO

Determinar el número de nodos del siguiente

árbol binario completo.

NN= (2^3) – 1

NN= 8 – 1

NN= 7


REPRESENTACIÓN DE

ÁRBOLES GENERALES

COMO BINARIOS

Existen tres pasos que se deben aplicar para la

conversión del árbol general al árbol binario.

PASO 1 Y 2

1) Enlazar los hijos decada nodo en formahorizontal (loshermanos).

2) Enlazar en formavertical el nodo padrecon el hijo que seencuentra más a laizquierda. Además,debe eliminarse elvinculo de ese padrecon el resto de sushijos.

PASO 3

Rotar el diagrama resultante, aproximadamente 45 grados

hacia la izquierda, y así se obtendrá el árbol binario

correspondientes.


CONDICIONES A CUMPLIR

Si la rama de la derecha de cada nodo, excepto el nodo raíz, esdistinta del vacío, se encuentra un nodo que era hermano deeste en el árbol.

Por ejemplo en la Figura A en comparación con la Figura C:

C era hermano de B.

D era hermano de C.

D era hermano de B.

E y F eran hermanos.

M y N eran hermanos.

H, I, J y K eran hermanos.


Si la rama izquierda de cada nodo (si esta es distinto del vacío),se encuentra un nodo que era hijo de éste en el árbol general.

Por ejemplo en la Figura A en comparación con la Figura C):

E era hijo de B.

F era hijo de B.

F era hermano de E.

B, C y D era hijos de A.

M y N eran hijos de G.

G era hijo de C.

CONDICIONES A CUMPLIR


REPRESENTACIÓN DE UN

BOSQUE COMO ÁRBOL

BINARIO

Un bosque representa un conjunto normalmente

ordenado de uno o más árboles generales.

PASOS

1)Enlazar de forma horizontal las raíces de los distintos árbolesgenerales.

2)Enlazarse los hijos de cada nodo en forma horizontal.

3)Enlazarse en forma vertical el nodo padre con el hijo que seencuentra más a la izquierda. Además se elimina el vinculo delpadre con el resto del sus hijos.

4)Por ultimo debe rotarse el diagrama resultante aproximadamente45° hacia la izquierda.

GRÁFICAS

Es una estructura de datos que permite representar

diferentes tipos de relaciones entre los objetos.


ELEMENTOS DE LAS

GRÁFICASNODOS:

También conocidos como vértices; almacenan información delobjeto.

ARCOS:

También llamados aristas; conectan un vértice con otro yrepresentan la relación entre dicha información.

DEFINICIÓN

Una gráfica G consta de dos conjuntos: V(G) y A(G).

Gráfica= (V, A)

V: simboliza el conjunto de vértices.

A: es el conjunto de aristas.


CONCEPTOSGRADO DE UN NODO

Es el número de aristas que apuntan al vértice.

Sino tiene aristas, es un vértice aislado.

LAZO O BUCLE

Es una arista que conecta a un nodo consigo.

CAMINO

Secuencia de n vértices que se debe seguir para llegar del nodo

origen al nodo destino.

CAMINO CERRADO

Es cerrado cuando el primer y último nodo son iguales.

CAMINO SIMPLE

Si todos sus nodos son distintos, con excepción del primero y el

segundo.

CICLO

Es un camino simple cerrado de longitud 3 o mayor.

CONCEPTOS

GRÁFICA CONEXA

Si existe un camino simple entre dos de sus nodos cualesquiera.

GRÁFICA ÁRBOL

Cuando es una grafica conexa sin ciclos.

GRÁFICA COMPLETA

Si cada vértice es adyacente a todos los demás vértices.

CONCEPTOS

GRÁFICA ETIQUETADA

Cuando sus aristas tienen un valor asignado.

MULTIGRÁFICA

Si al menos dos de sus vértices están conectados por dos aristas.

SUBGRÁFICA

Donde cada arista prima es incidente con el vértice primo.

G= (V, A); G`= (V`, A`)

CONCEPTOS

En la gráfica a existe un lazo o bucle en el

vértice d.

Es decir a = (d, d).

OTROS CONCEPTOS


estructura de datos - árboles y grafos

Engineering