estructuras de datos avanzadas Árboles y grafos. son estructuras compejas no lineales y dinámicas...

ESTRUCTURAS DE DATOS AVANZADAS

Árboles y GrafosÁrboles y Grafos

Son estructuras compejas no lineales y dinámicas donde en su ejecución varia el número de elementos y uso de memoria a lo largo del programa.

Entre este tipo de estructuras podemos mencionar a los árboles, grafos y redes.

¿Qué son las estructuras de datos avanzadas?

¿Qué es un Árbol?• Son Estructuras de Datos no lineales. Es una colección de nodos

donde cada uno, además de almacenar información, guarda la dirección de sus sucesores

• Es una estructura de datos jerárquica.• La relación entre los elementos es de uno a muchos.

Terminología

• Nodo: Cada elemento en un árbol.• Nodo Raíz: Primer elemento agregado al árbol.

B

A

D E

H

F

K

G

C

Nodo Raíz

Más terminología

• Nodo Padre: Se le llama así al nodo predecesor de un elemento.• Nodo Hijo: Es el nodo sucesor de un elemento.• Hermanos: Nodos que tienen el mismo nodo padre.

B

A

D E

H

F

K

G

CNodo Padre

F y G son Nodos Hijos de CF y G son hermanos

Más terminología

• Nodo Hoja: Aquel nodo que no tiene hijos.

B

A

D E

H

F

K

G

C

D, H, F y K son Nodos Hojas

Más terminología

• Subárbol: Todos los nodos descendientes por la izquierda o derecha de un nodo.

B

A

D E

H

F

K

G

C

Subárbol derecho de C

Subárbol izquierdo de C

Altura y Niveles

Nivel 0

Nivel 1

Nivel 2

Nivel 3

Altura del árbol = 4

B

A

D E

H

F

K

G

C

La Altura es la cantidad de niveles.

Elementos del árbol• Nodo Raíz, Nodos Hijos, Nodos Hermanos, Altura, Recorridos,

Dirección.• Todo Árbol tiene un solo Nodo Raíz.• Los Árboles pueden tener o no Nodos Hijos. En caso de

tenerlos, pueden existir Nodos Hermanos. • Si únicamente tiene un Nodo Raíz, su Altura = 0 y su Nivel = 1.• Los Recorridos pueden ser en preorden, postorden y en

orden.• Un Árbol puede recorrerse en dirección Top-Down de arriba

abajo, de abajo arriba, (Down-Top). A partir de su rama Izquierda o a partir de su rama Derecha.

Tipos de árbol

Árbol Binario de Búsqueda (ABB)

• Este tipo de árbol permite almacenar información ordenada.

• Reglas a cumplir:– Cada nodo del árbol puede tener 0, 1 ó 2 hijos.– Los descendientes izquierdos deben tener un

valor menor al padre.– Los descendientes derechos deben tener un valor

mayor al padre.

Ejemplos de ABB…

13

21

5 18

15

25

40

36

3321

30

32

43

41

33

¿Por qué no son ABB?

13

21

17 18

15

25

40

22

331

5

2 4

6

Definición en C++ del ABB…

struct nodo{ int nro; struct nodo *izq, *der;};

typedef struct nodo *ABB;/* es un apuntador de tipo nodo que hemos llamado ABB, que ulitizaremos para mayor facilidad de creacion de variables */

Proceso para buscar un nodo...

13

21

10 18 2540

33

¿El 25 es mayor o menor que el 21?

Buscar el 25

13

21

10 18 25 40

33¿El 25 es mayor o menor que el 33?

13

21

10 18 25 40

33

Encontrado

Paso1

Paso2

Paso3

Proceso para agregar nodos...

• Reglas: (busca y agrega hojas)– El valor a insertar no existe en el árbol.– El nuevo nodo será un Nodo Hoja del árbol.

• Procedimiento1. Buscar el Nodo Padre del nodo a agregar.2. Agregar el nodo hoja.

Ejemplo

13

21

10 18 2540

33

¿El 26 es mayor o menor que el 21?

Agregar el valor 26

13

21

10 18 25 40

33¿El 26 es mayor o menor que el 33?

13

21

10 18 25 40

33

Se encontró el Nodo Padre

Paso1

Paso2

Paso3

13

21

10 18 25 40

33

Agregar el nodo

Paso4

26

Recorrido de árboles

• Es el proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos).

• Tales recorridos están clasificados por el orden en el cual son visitados los nodos.

Recorrido de árbolesPreorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:1.Visite la raíz2.Atraviese el sub-árbol izquierdo3.Atraviese el sub-árbol derechoInorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:1.Atraviese el sub-árbol izquierdo2.Visite la raíz3.Atraviese el sub-árbol derechoPostorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:1.Atraviese el sub-árbol izquierdo2.Atraviese el sub-árbol derecho3.Visite la raíz

¿Qué es un grafo?• Son Estructuras de Datos complejas no lineales,

en las cuales cada elemento puede tener cero o más sucesores y cero o más predecesores. Están formados por nodos (vértices: representan información) y por arcos (aristas: relaciones entre la información) .

Tipos de grafos

Grafos dirigidos• En un grafo generalizado su dirección puede estar

especificada o no. Por el contrario en el grafo dirigido o también conocido como digrafo, el conjunto de sus aristas tienen una dirección definida y está determinado por un par de conjuntos G=(V,A) donde V es un conjunto vacío llamado vértices o nodos y A es un conjunto de pares ordenados de elementos de V llamados aristas o arcos que van del primer al segundo nodo dentro del par.

Grafos ponderados• Son útiles para medir las distancias en un mapa. • Por ejemplo el caso de un repartidor de muebles que tiene que

recorrer varias ciudades de México conectadas entre si por las carreteras que hay entre la Ciudad de México, Guadalajara y Monterrey, su misión es optimizar la distancia recorrida (minimizar el tiempo, prever tráfico y atascos). El grafo correspondiente tendrá como vértices estas ciudades y como aristas la red de carreteras y la valoración, peso o ponderación será la distancia que hay entre ellas. Para tal efecto, es preciso atribuir a cada arista un número específico, ponderación, peso o coste según el contexto, y se obtiene así un grafo valuado o ponderado.

• Un grafo ponderado o grafo con valores o pesos es un grafo G (V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso ( w: E->R+ ) donde el peso de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.

Gráfica de grafo ponderado

Operaciones con Grafos• Insertar vértice (nodo). Es La operación de inserción de un nuevo nodo.

• Insertar arista. (arco). 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 l nodo • Eliminar arista. Eliminación de la relación, se borra un arco del grafo.

• 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.