sábado, 15 de junio de 2019

Árboles - Grafos

        Árboles - Grafos

Introducción:  

En este blog abordaremos temas básicos de Árboles como su definición, usos y tipos de recorridos.

 Árbol

Definición:

Un árbol es un grafo acíclico conexo. En particular, un árbol no tiene lazos ni aristas paralelas.
Ejemplos:
Consideraremos cualquier grafo conexo G. Un subgrafo T de G se llama un árbol generador si T es un árbol y si T incluye a todos los vértices de G, es decir, V(T) = V(G). En otras palabras, T es un árbol que se obtiene quitando algunas aristas de G, posiblemente, pero manteniendo todos los vértices.
T1
T2
T3

Usos:

Ejemplos:
1.      Un árbol binario de búsqueda es una estructura que se utiliza para determinar con rapidez el valor o el lugar de los objetos, que estén ordenadas linealmente como números o archivos alfabetizados. Ejemplo: árbol binario de búsqueda para buscar un número en {1,2,3,…,15}.
Los números en círculo son llaves. Dado un número en el conjunto, primero se le compara con 8: si es menor que 8 pasa a la llave 4; si es mayor que 8 pasa a la llave 12; si es igual a 8 la búsqueda terminó. Se produce de esta manera bajando por el árbol hasta que se encuentra el número.
2.      Estructuras de datos para diagnóstico o identificación se pueden ver con frecuencia como árboles enraizados. 
Ejemplo: 

Para poder utilizar esta estructura de datos empezamos por la parte superior, y procedemos de vértice en vértice tomando la rama apropiada en caso de que esos sean los síntomas del paciente. La hoja final del camino da el nombre del estado o estados más probables para los síntomas dados.
El mismo tipo de árbol enraizado es utilizado en las guías para identificar hongos, pájaros, flores silvestres, etc. 
3.      Las cadenas de mando de una organización se pueden representar con árboles enraizados. Ejemplo: Jerarquía de una universidad.

Tipos de recorridos de un árbol:

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden específico, los recorridos nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo.
Básicamente podemos catalogar las búsquedas en dos tipos, la búsqueda en profundidad y la búsqueda en amplitud.
Búsqueda en profundidad:
Recorrido Pre-order: La raíz se enlista primero y los subárboles se enlistan en el orden de sus raíces. Por la forma en que dibujamos un árbol enraizado ordenado, nos referimos al orden de izquierda a derecha.
Ejemplo:
En la imagen podemos ver el orden en que es recorrido el árbol iniciando desde la Raíz.
Recorrido Pos-order: Los subárboles se enlistan primero en el orden y después se enlistan las raíces al final.
Ejemplo:
En la imagen podemos observar cómo se realiza el recorrido en Pos-Order, Sin embargo es importante notar que el primer nodo que se imprime no es la Raíz pues en este recorrido la Raíz de cada Sub-Árbol es procesado al final, ya que toda su descendencia ha sido procesada.
Recorrido in-order: Para árboles enraizados, el recorrido in-order enliste la raíz entre los subárboles a su izquierda y a su derecha. 
En la imagen se muestra como es el recorrido In-Order, Podemos apreciar que la Raíz no es el primero elemento en ser impreso pues este recorrido recorre su rama izquierda, luego la raíz del sub-árbol y luego la rama derecha.
Búsqueda en amplitud: Se recorre primero la raíz, luego se recorren los demás nodos ordenados por el nivel al que pertenecen en orden de Izquierda a derecha.  Este tipo de búsqueda se caracteriza por que la búsqueda se hace nivel por nivel y de izquierda a derecha.
En la imagen se observa como es que un nodo es buscado mediante la búsqueda en profundidad.
Los pasos para hacer el recorrido es el siguiente:
1.      Se agrega la Raíz a la cola de nodos por visitar
2.      Mientras que la cola no este vacía se saca el primer elemento de la cola y continuamos con el paso 3, Pero; si la cola está vacía entonces nos vamos al paso 5.
3.      Se valida si el elemento sacado de la pila es el que estamos buscando, Si lo es, entonces hemos terminado, Si no lo es se agregan todos los hijos del nodo a la pila de nodos pendientes por procesar.
4.      Regresamos al paso 2.
5.      Terminamos sin un resultado.

Referencias

KENNET, A. Ross y CHARLES, R.B. Wright.(1999).Matemáticas Discretas.México. México: Prentice-Hall Hispanoamericana, S.A
Blancarte, Oscar.(2014).Oscar Blancarte Software architect. https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/


Este blog fue elaborado por:
     Cabrera, Irina y Vallejos, Agustín.(2019)