Tema 4 - Facultad de Ciencias Exactas y Naturales y ...exa.unne.edu.ar/informatica/.../Tema_4_arboles_y_grafos_Teoria.pdf · 4.1.5 Implementación de un Arbol Binario Implementación

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

Estructura de datos no linealesArboles y Grafos

Tema 4


4.1 Arboles4.1.1. Introducción

Las estructuras de datos vistas en apartados anteriores son de tipo lineales, dado que a cada elemento le seguía siempre otro elemento. Esa linealidad es típica en cadenas, listas, array, pilas, colas, campos en los registros, etc.-.

Pero existen otras estructuras de datos con características no lineales, es decir, se introduce el concepto de bifurcación dado que en estas estructuras cada elemento puede tener diferentes siguientes elementos. Estas estructuras reciben el nombre de árboles y grafos, otros autores le dan el nombre de estructuras multi-enlazadas.

Si nos referimos a estructuras de datos, se dijo en el tema anterior que las pilas, colas y listas son estructuras lineales, puesto que en todas ellas cada elemento tiene un único elemento anterior y un único elemento posterior. Pero, además, existe estructuras de datos no lineales, en las que esta restricción desaparece. Esto es, en estas estructuras cada elemento puede tener varios anteriores y/o varios posteriores.


4.1 Arboles4.1.1. Introducción

DefiniciónUn árbol es una estructura de datos no lineal y homogénea en el que cada elemento puede tener varios elementos posteriores, pero tan sólo puede tener un elemento anterior.


4.1 Arboles4.1.2 Representación

Gráficamente puede representarse una estructura de árbol de diferentes formas y serán todas ellas equivalentes.

A

B C

D E F

G H

AB

D

E

C

F

G

H

( A ( B ( D , E ) ), C ( F ( G , H ) ) )

a) Diagrama de Venn

b) Anidación de Paréntesis

d) Grafo

A

B

E

D

C

F

G

H

c) Identada

a) su representación está dada por un diagrama de Venn. b) por medio de anidación de paréntesis. c) por medio de la representación indentada d) por medio de grafos.


4.1 Arboles4.1.3 Terminologia básica

A

B C

D E F

A

B

C

A

Ejemplo 1 Ejemplo 2 Ejemplo 3

G H

Nodo Padre de un nodo N es aquel que apunta al mismo. En un árbol cada nodo sólo puede tener un padre. En el ejemplo 1, A es el padre de B y C, y a su vez, B es el padre de D.Nodo Hijo de otro nodo A hijo es cualquier nodo apuntado por el nodo A. Un nodo puede tener varios hijos. En el ejemplo 1, B y C son los nodos hijos de A y todos los nodos tienen uno o dos hijos.Nodo Raíz es el único del árbol que no tiene padre. En la representación que hemos utilizado, el nodo raíz es el que se encuentra en la parte superior del árbol: A.Hojas son todos los nodos que no tienen hijos. En la representación del ejemplo 1 son hojas los nodos situados en la parte inferior: D, G, H y F.


4.1 Arboles4.1.3 Terminologia básica

A

B C

D E F

A

B

C

A


G H

Nodos Interiores son los nodos que no son ni el nodo raíz, ni nodos hoja. En el ejemplo 1, son nodos interiores B, C y E.Camino es una secuencia de nodos, en el que dos nodos consecutivos cualesquiera son padre e hijo. En el ejemplo 1 A-B-D es un camino, al igual que E-G y C-E-H.Rama es un camino desde el nodo raíz a una hoja. En el ejemplo 1, A-C-E-G y AC-F son ramas.Altura es el máximo número de nodos de las ramas del árbol. Dicho en otros términos, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. La altura del árbol del ejemplo 1 es 4, ya que esa es la longitud de la rama A-C-E-H, que junto a A-C-E-G son las dos más largas.


4.1 Arboles4.1.3 Terminología básica

A

B C

D E F

A

B

C

A


G H

Grado es el número máximo de hijos que tienen los nodos del árbol. Así, en el ejemplo anterior el árbol es de grado dos. Démonos cuenta de que una lista no es más que un árbol de grado uno, tal y como podemos ver en los ejemplos 2 y 3.Nivel de un nodo, es el número de nodos del camino desde la raíz hasta dicho nodo. En el árbol del ejemplo 1, A tiene nivel 1; B y C tienen nivel 2; D, E y F tienen nivel 3 y G y H tienen nivel 4.Bosque colección de dos o más árboles.


4.1 Arboles4.1.4 Arbol Binario

Existe un tipo de arbol denominado arbol binario que puede ser implementado facilmente en la computadora.

DefinicionUn arbol binario es un conjunto finito de cero o mas nodos tales que:● Existe un nodo denominado raiz del arbol.● Cada nodo puede tener 0,1, o 2 subarboles, conocidos como subarbol izquierdo y subarbol derecho.

La figura representa diferentes tipos de arboles binarios: A) expresion de arbol A+B/C, y B) son arboles de operación aritmetica con valores enteros

+

/ A

5

+

B C

A) B)

100

A

B C

D E F

G H

C)



Si tomamos el grafico C) de la figura vemos que es un árbol binario, ya que cada nodo tiene como máximo dos hijos. Démonos cuenta que en cualquier árbol, no sólo en los binarios, si eliminamos el nodo raíz, obtenemos dos árboles. - Aquel que colgaba del enlace izquierdo del nodo raíz se denomina subárbol izquierdo - Aquel que colgaba del enlace derecho se denomina subárbol derecho.

Además, en un árbol binario, todos los subárboles son también árboles binarios.De hecho, a partir de cualquier nodo de un árbol podemos definir un nuevo árbol sin más que considerarlo como su nodo raíz. Por tanto, cada nodo tiene asociados un subárbol derecho y uno izquierdo.

+

/ A

5

+

B C

A) B)

100

A

B C

D E F

G H

C)



Existen algunos tipos especiales de árboles binarios en función de ciertas propiedades. Así por ejemplo:

Árbol binario equilibrado es aquel en el que en todos sus nodos se cumple la siguiente propiedad,

altura(subárbol_izquierdo) - altura(subárbol_derecho) | <= 1.

Así, el árbol del ejemplo 1 de la figura sería un árbol binario equilibrado, mientras el del ejemplo 2 no lo sería. En el segundo caso el subárbol izquierdo de A tiene una altura 2, mientras su subárbol derecho tiene una altura 0.

A

B C

D E F

A

B

C

A


G H



Árbol binario completo es aquel en el que todos los nodos tienen dos hijos y todas las hojas están en el mismo nivel.

Se denomina completo porque cada nodo, excepto las hojas, tiene el máximo de hijos que puede tener.

En estos árboles se cumple que en el nivel k hay 2k-1 nodos y que, en total, si la altura es h, entonces hay 2h - 1 nodos.

A

B C

D F GE

La figura representa un árbol binario completo. En el nivel 1 tenemos 20 = 1 nodosEn el nivel 2 tenemos 21 = 2 nodosEn el nivel 3 tenemos 22=4 nodos.En total el árbol es de altura 3 y por tanto contiene 23-1 = 7 nodos.


4.1 Arboles4.1.5 Implementación de un Arbol Binario

Al igual que ocurre en el caso de las listas, podemos implementar un árbol binario mediante ● estructuras estáticas ● estructuras dinámicas.

En ambos casos, cada nodo del árbol contendrá tres valores:

● La información de un tipobase dado contenida en el nodo.● Un enlace al hijo derecho (raíz del subárbol derecho)● Un enlace al hijo izquierdo (raíz del subárbol izquierdo)



Implementación estática mediante un vectorPara realizar la implementación estática del árbol binario utilizamos una estrategia similar a la usada en las listas, en las que simulábamos la memoria dinámica mediante el uso de vectores. - Cada nodo es un registro con los tres campos especificados anteriormente- Todos los nodos se almacenan en un vector de registros. - Para implementar los enlaces utilizaremos números enteros que serán los índices en el vector donde se encuentran los hijos izquierdo y derecho.

Al igual que ocurre en el caso de las listas, las componentes vacías del vector se enlazan formando una lista. Para ello podemos usar como campo de enlace, tanto el correspondiente a los hijos izquierdos como a los derechos.



Implementación estática mediante un vector

No vamos a detallar la implementación de todas las operaciones mediante vectores, sino que tan sólo mostraremos la estructura de datos en Pascal que usaremos para llevar a cabo esta implementación.

CONST MAX = ... {Tamaño del vector y máximo número de nodos del árbol}TYPE Posicion = 0 .. MAX;Elemento = RECORD info: <TipoBase>; der, izq: PosicionEND;

TipoArbolB= RECORD raiz, vacios: Posicion; mem : ARRAY [1..MAX] OF ElementoEND;



Implementación estática mediante un vector

La representación mediante esta estructura estática del árbol de la figura vendría dada por el siguiente vector de registros:

Raiz=1 Vacios= 51 2 3 4 5 6 7 8 9 10 11 12A B C E F D H G Inf3 0 9 6 12 11 2 0 0 0 0 7 Izq4 0 8 10 0 0 0 0 Der

A

B C

D E F

G H

En el ejemplo anterior hemos utilizado el 0 para indicar un enlace que no apunta a ningún nodo. Las componentes del vector cuyos campos izq y der contienen un 0 son las hojas del árbol. Mientras la componente 2 es en este caso la última de la lista de componentes vacías.



Implementación dinámica mediante punterosLa representación de cada nodo en esta implementación será también un registro de tres campos, pero en este caso los enlaces serán punteros a los subárboles izquierdo y derecho de cada nodo. Por lo tanto, la estructura de datos en Pascal para definir un árbol binario será la siguiente:

TYPETArbol = ^Nodo;Nodo = RECORD

info: <tipobase>;izq, der: TArbol

END;De este modo, un árbol se identifica con un puntero a su nodo raíz, a través del cual podemos acceder a sus distintos nodos.



Implementación dinámica mediante punteros

Recorrido de un Árbol binario

Recorrer un árbol consiste en acceder una sola vez a todos sus nodos.

En el caso de los árboles binarios, el recorrido de sus distintos nodos se debe realizar en tres pasos:● acceder a la información de un nodo dado,● acceder a la información del subárbol izquierdo de dicho nodo,● acceder a la información del subárbol derecho de dicho nodo.

Imponiendo la restricción de que el subárbol izquierdo se recorre siempre antes que el derecho, esta forma de proceder da lugar a tres tipos de recorrido, que se diferencian por el orden en el que se realizan estos tres pasos.




Recorrido de un Árbol binarioPreorden: primero se accede a la información del nodo, después al subárbol izquierdo y después al derecho.

A-B-D-C-E-G-H-F Recorrido Preorden

A

B C

D E F

G H




Recorrido de un Árbol binarioInorden: primero se accede a la información del subárbol izquierdo, después se accede a la información del nodo y, por último, se accede a la información del subárbol derecho.

D-B-A-G-E-H-C-FRecorrido Inorden

A

B C

D E F

G H




Recorrido de un Árbol binarioPostorden: primero se accede a la información del subárbol izquierdo, después a la del subárbol derecho y, por último, se accede a la información del nodo.

D-B-G-H-E-F-C-ARecorrido Postorden

A

B C

D E F

G H


4.1 Arboles4.1.6 Arbol Binario de Búsqueda

Imaginémonos que queremos encontrar un elemento en una lista ordenada. Para hacerlo deberemos recorrer sus elementos desde el primero hasta encontrar el elemento buscado o uno mayor que este. El coste medio de esta operación involucrará en un caso medio el recorrido y comparación de n/2 nodos, y un coste en el caso peor O(n). Si en lugar de utilizar una lista, estructuramos la información de modo adecuado en un árbol, podremos reducir el coste de la búsqueda a O(log2n).

Para hacernos una idea de lo que supone esta reducción del coste, supongamos que queremos encontrar un elemento entre 1000. Si almacenamos toda la información en una lista ordenada, esta búsqueda puede suponernos recorrer y comparar hasta 1000 nodos. Si esta misma información la almacenamos en un árbol binario de búsqueda, el coste máximo será de log2(1000)<10. Hemos reducido el coste de 1000 a 10 al cambiar la estructura de datos utilizada para almacenar la información.Tal y como hemos dicho, no basta con almacenar la información en un árbol para facilitar la búsqueda, debemos utilizar un tipo especial de árbol: un árbol binario de búsqueda. Si además queremos que esta búsqueda sea lo más eficiente posible debemos utilizar árboles de búsqueda binarios equilibrados.



DefiniciónUn árbol binario de búsqueda es una estructura de datos de tipo árbol binario en el que para todos sus nodos, el hijo izquierdo, si existe, contiene un valor menor que el nodo padre y el hijo derecho, si existe, contiene un valor mayor que el del nodo padre.

5

3 9

1 7 10

6 8



Búsqueda de un elemento

La operación de búsqueda en un árbol binario de búsqueda es bastante sencilla de entender.

Supongamos que buscamos un elemento x en el árbol. Lo primero que haremos será comprobar si se encuentra en el nodo raíz. Si no es así, si el elemento buscado es menor que el contenido en el nodo raíz sabremos que, de estar en el árbol, se encuentra en el subárbol izquierdo. Si el elemento buscado es mayor que el contenido en el nodo raíz sabremos que, de estar en el árbol, se encuentra en el subárbol derecho. Para continuar la búsqueda en el subárbol adecuado aplicaremos recursivamente el mismo razonamiento. Por lo tanto, el esquema del algoritmo BuscarNodo será el siguiente:● Si el valor del nodo actual es igual al valor buscado, lo hemos encontrado.● Si el valor buscado es menor que el del nodo actual, deberemos inspeccionar el subárbol izquierdo.● Si el valor buscado es mayor que el del nodo actual, deberemos inspeccionar el subárbol derecho.



Insertar un elemento NIL

Arb

ol v

acio

5

Inse

rtar 5

5

9

Inse

rtar 9

5

3 9

Inse

rtar 3

5

3 9

7

Inse

rtar 7

5

3 9

7

8

Inse

rtar 8

5

3 9

7 10

8

Inse

rtar 1

0

5

3 9

7 10

6 8

Inse

rtar 6

5

3 9

1 7 10

6 8

Inse

rtar 1



Eliminar un elemento

5

3 9

1 7 10

6 8

Arbo

l Ini

cial

5

3 9

1 7 10

6

Sup

rimir

8 (C

aso

a)

5

3 9

1 6 10

Supr

imir

7 (C

aso

b)

1

3 9

6 10

Supr

imir

5 (C

aso

c)

1

3 6

10

Supr

imir

9 (C

aso

c)

3

6

10

Sup

rimir

1 (C

aso

c)



Arboles de expresiones aritmeticas Por ejemplo, la siguiente expresion dada en notacion habitual

((3*(4+5))-7:2)):6

:

- 6

* :

7 23 +

4 5


4.2 Grafos4.2.1 Introducción

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana,algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matemàticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. (Véase la figura). En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (vértices) con líneas conectándolos (arcos).

a) Red de computadoras

b) Red de Vías áereas



Los grafos tienen un campo amplio de aplicaciones. En el estudio de los mismos se han interesados los matemáticos hace muchos siglos atrás. También son usados como herramientas para definir sistemas expertos y otros modelos utilizados en el área de la inteligencia artificial.Definicion

Un grafo es un conjunto de puntos o nodos, y un conjunto de líneas tal que cada una de ellas une un punto a otro punto.

Un grafo G es un conjunto en el que hay definida una relación binaria,es decir,G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y

es una relación binaria a cuyos elementos denominaremos arcos o aristas.



Dados ,puede ocurrir que:

en cuyo caso diremos que x e y están unidos mediante un arco,y

en cuyo caso diremos que no lo están. Si las aristas tienen asociada una dirección (las aristas (x,y) y (y,x) no son equivalentes) diremos que el grafo es dirigido, en otro caso ((x,y)=(y,x)) diremos que el grafo es no dirigido.



Por ejemplo, sea el grafo G de la figura

V(G1) = {a,b,c,d}A(G1) = {(a,b),(a,d),(b,c),(b,d)}

a

b

c

d


4.2 Grafos4.2.2 Representación

Un grafo puede ser representado de varias formas equivalentes que pongan de manifiesto en mayor o menor medida determinadas características. Las formas de representación mas comunes son:

- Simbólicamente: Como ya se ha descripto en el apartado anterior, como un par (V,A), donde V es un conjunto de variables y A es un conjunto de aristas entre pares de variables.

- Gráficamente: por medio de un diagrama formado por un conjunto de nodos (uno para cada variable) y un conjunto de líneas (una para cada arista del conjunto A).

- Numéricamente: utilizando cierto tipos de matrices



Existe una clasificación de grafos según sus aristas. Por tanto, las aristas de un grafo pueden ser dirigidas o no dirigidas, dependiendo de si se considera o no, el orden de los nodos. En la práctica esta distinción dependerá de la importancia del orden en que se relacionen los objetos.

Por lo tanto y teniendo en cuenta lo mencionado anteriormente, se considerarán dos tipos de grafos:

- Dirigidos: cuando todas las aristas son dirigidas.- No Dirigidos: cuando todas las aristas no son dirigidas.



Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido.Por el contrario,la red de carreteras de un país representa en general un grafo no dirigido,puesto que una misma carretera puede ser recorrida en ambos sentidos.

Entonces, en un grafo dirigido es importante el orden del par de nodos que definen cada arista, mientras que en un grafo no dirigido, el orden carece de importancia. La figura muestra gráficas de grafos dirigidos y no dirigidos A

B C

ED

F G

a)

B

C

A

E

D

G

F

b)


4.2 Grafos4.2.3 Definición y Terminología

Grafo Dirigido:

Es un par G = (V;A) donde V es un conjunto finito de elementos llamados vertices y A V x V es un conjunto finito de pares ordenados de vertices llamados aristas.

Si a = (u; v) es una arista de G, se dice que a entra o incide en v y que a sale o emerge de u.

Grafo no Dirigido:Es un par G = (A; V ) donde V es un conjunto finito de vertices y

es un conjunto de “pares no ordenados" de vertices.Equivalentemente, G es un Grafo no Dirigido si G es un Grafo Dirigido y

sies un arco no dirigido, se dice que a une a u y v y que a incide en u y en v.



Grado: Para todo vertice v, - Grado de Entrada es el numero de aristas que inciden en v; - Grado de Salida es el numero de aristas que emergen de v; - Grado es la suma de los grados de entrada y salida de v. - Grado de un Grafo es el maximo grado de sus vertices.

Camino: es una secuencia de uno o mas arcos que conectan dos nodos.

Camino Simple: es un camino en el que todos sus vertices son distintos.



Grafo conectado: cuando existe siempre un camino que une dos vertices cualesquiera

Grafo desconectado: cuando existen vèrtices que no estan unidos por un camino.

Grafo completo: es aquel en que cada vèrtice esta conectado con todos y cada uno de los restantes nodos. Si existen n vèrtices, habrà n(n-1) aristas en un grafo completo y dirigido, y n(n-1)/2 aristas en un grafo no dirigido completo.


4.2 Grafos4.2.4 Representacion numérica de grafos

Existen dos tecnicas estandar para presentar numericamente un grafo G: - matriz de adyacencia (mediante arreglos)

- lista de adyacencia (mediante punteros/listas enlazadas)



Matriz de adyacencias

Sea G = (V,A) un grafo de n nodos, suponemos que los nodos V = {u1,...,un} están ordenados y podemos representarlos por sus ordinales {1,2,...,n}. La representación de los arcos se hace con una matriz A de nxn elementos aij definida:aij 1 si hay arco (ui,uj)

0 si no hay arco (ui,uj)

La matriz A se denomina matriz de adyacencias del grafo G.Mediante sencillas manipulaciones algebraicas de la matriz de adyacencia se pueden obtener algunas características del grafo como, por ejemplo, el número de caminos distintos que unen dos nodos, comprobar si el grafo es conexo, usar la diagonal principal de la matriz de adyacencia para representar la existencia de un vértice, etc.-




Cuando aij = 0, entonces no existe ninguna arista del nodo Xi al nodo Xj , o que los nodos son adyacentes, de ahí el nombre de la matriz.

La matriz A contiene toda la información topológica del grafo asociado; por tanto, esta matriz caracteriza al grafo. Notar que:

1) La matriz de adyacencias de un grafo no dirigido es simétrica2) Dado que Vij no pertenece a V para todos los valores de i, los elementos diagonales de A son nulos.3) La matriz de adyacencia de un grafo no dirigido completo debe contener un 1 en todos los elementos no diagonales.

La matriz de adyacencia permite comprobar si existe algún camino entre cada par de nodos. También puede calcularse la longitud de todos los caminos que unan cada par de nodos. Para comprobar esto existen teoremas que no son objetos de nuestro estudio.




Graficamente

x1

x4

x2 x3 A =

X X

x1 x2 x3 x4

x1

X X Xx2

Xx3

X Xx4

0 1 0 1

1 0 1 1

0 1 0 0

1 1 0 0




Ejemplo

1 2

5 4

3

0 1 0 0 11 0 1 1 10 1 0 1 00 1 1 0 11 1 0 1 0



Lista de adyacencias

Este mètodo es util de usarlo cuando un grafo tiene muchos vertices y pocas aristas. En esta representación se utiliza una lista enlazada por cada vertice vdel grafo que tenga vertices adyacentes desde el.

El grafo completo incluye dos partes: - un directorio - un conjunto de listas enlazadas.

➔Hay una entrada en el directorio por cada nodo del grafo. ➔La entrada al directorio del nodo i apunta a una lista enlazada que representa los nodos que son conectados al nodo i. ➔Cada registro de la lista enlazada tiene dos campos: - un identificador de nodo- un enlace al siguiente elemento de la lista➔La lista enlazada representa arcos.



Lista de adyacencias

Ejemplo

2

5 -

5

2 -

4 -

4 -

6 -

1

2

3

4

5

1 2

4 5

3

6

6 -6

0 1 0 1 0 00 0 0 0 1 00 0 0 0 1 10 1 0 0 0 00 0 0 1 0 00 0 0 0 0 1

Grafo Dirigido Lista de Adyacencia Matriz de Adyacencia

Documents

Tema 4 - Facultad de Ciencias Exactas y Naturales y ...exa.unne.edu.ar/informatica/.../Tema_4_arboles_y_grafos_Teoria.pdf · 4.1.5 Implementación de un Arbol Binario Implementación