Á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
T3Usos:
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)
