Estructura de datos – Árboles

Fig. 9:

Los Árboles son las estructuras de datos mas utilizadas, pero también una de las mas complejas, Los Árboles se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal como las Listas Ligadas, Colas,Pilas,etc., de las cuales ya hemos hablado en días pasados.

árboles
Fig. 1: La imagen muestra la diferencia entra las estructuras de datos lineas y las no lineales como lo son los Árboles.

 

Datos importantes de los Árboles

Para comprender mejor que es un árbol comenzaremos explicando como está estructurado.

Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.

Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.

Nodo Padre: Se utiliza este termino para llamar a todos aquellos nodos que tiene al menos un hijo.

Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.

Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en común dentro de la estructura.

Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura.

Nodo Rama: Estos son todos aquellos nodos que no son la raíz  y que ademas tiene al menos un hijo.

 

árboles
Fig. 2: La imagen muestra de forma gráfica cuales son los nodos Raíz, Rama, Hoja.
árboles
Fig.3: La siguiente imagen muestra de forma gráfica los nodos Padre, Hijo y Hermanos

Los arboles a demas de los nodos tiene otras propiedades importantes que son utilizadas en diferente ámbitos los cuales son:

Nivel: Nos referimos como nivel a cada generación dentro del árbol. Por ejemplo, cuando a un nodo hoja le agregamos un hijo, el nodo hoja pasa a ser un nodo rama pero a demas el árbol crece una generación por lo que el Árbol tiene un nivel mas.Cada generación tiene un número de Nivel distinto que las demas generaciones.

  • Un árbol vacío tiene 0 niveles
  • El nivel de la Raíz es 1
  • El nivel de cada nodo se calculado contando cuantos nodos existen sobre el, hasta llegar a la raíz + 1, y de forma inversa también se podría, contar cuantos nodos existes desde la raíz hasta el nodo buscado + 1.

Altura: Le llamamos Altura al número máximo de niveles de un Árbol.

árboles
Fig. 4: En la imagen se muestran los Niveles y la Altura de un Árbol.

La altura es calculado mediante recursividad tomando el nivel mas grande de los dos sub-árboles de forma recursiva de la siguiente manera:

altura = max(altura(hijo1), altura(hijo2),altura(hijoN)) + 1

Peso: Conocemos como peso a el número de nodos que tiene un Árbol. Este factor es importante por que nos da una idea del tamaño del árbol y el tamaño en memoria que nos puede ocupar en tiempo de ejecución(Complejidad Espacial en análisis de algoritmos.)

árboles
Fig. 5: La imagen nos muestra como se calcula el peso de un Árbol, el cual es la suma de todos sus nodos, sin importar el orden en que sean contados.

El peso se puede calcular mediante cualquier tipo de recorrido el cual valla contando los nodo a medida que avanza sobre la estructura. El peso es un árbol es igual a la suma del peso de los sub-árboles hijos + 1

peso = peso(hijo1) + peso(hijo2) + peso(hijoN)+ 1

Nota: Los tipos de recorridos los veremos mas adelante.

Orden: El Orden de un árbol es el número máximo de hijos que puede tener un Nodo.

árboles
Fig. 6: Imagen que nuestra dos Árboles con Orden = 2(Izquierda) y un segundo con Orden = 3(Derecha).

Notemos que un Árbol con Orden = 1 no tendría sentido ya que seria una estructura lineal. ya que cada nodo solo podría tener un Hijo y tendríamos un Árbol como la Imagen de la Fig.1.

Este valor no lo calculamos, si no que ya lo debemos conocer cuando diseñamos nuestra estructura, ya que si queremos calcular esto lo que obtendremos es el grado(hablamos de el continuación).

Grado: El grado se refiere al número mayor de hijos que tiene alguno de los nodos del Árbol y esta limitado por el Orden, ya que este indica el número máximo de hijos que puede tener un nodo.

árboles
Fig. 7: En la imagen podemos apreciar un Árbol con grado 2(Izquierda) y un otro con grado 3(Derecha).

El grado se calcula contando de forma recursiva el número de hijos de cada sub-árbol hijo y el numero de hijos del nodo actual para tomar el mayor, esta operación se hace de forma recursiva para recorrer todo el árbol.

grado = max(contarHijos(hijo1),contarHijos(hijo2), contarHijos(hijoN), contarHijos(this))

Sub-Árbol: Conocemos como Sub-Árbol a todo Árbol generado a partir de una sección determinada del Árbol, Por lo que podemos decir que un Árbol es un nodo Raíz con N Sub-Árboles.

árboles
Fig. 8: En la imagen de puede apreciar que un Árbol esta compuesto por una seria de Sub-Arboles los cual conforman toda la estructura.

Existen escenarios donde podemos sacar un Sub-Árboles del Árbol para procesarlo de forma separada, de esta forma el Sub-Árboles pasa a ser un Árbol independiente, También podemos eliminar Sub-Árboles completos, Agregarlos,entre otras operaciones.

Árbol n-ario

los arboles n-arios son aquellos arboles donde el número máximo de hijos por nodo es de N, en la figura 7 podemos apreciar dos árboles con grado 2 y grado 3, estos dos arboles también los podemos definir como Árbol n-ario con n = 2 y n=3 respectivamente.

Árboles binarios

Esta estructura se caracteriza por que cada nodo solo puede tener máximo 2 hijo, dicho de otra manera es un Árbol n-ario de Grado 2.

árboles
Fig. 9: En la imagen podemos apreciar un Árbol Binario.

Árbol binario lleno: Es aquel que el que todos los nodos tiene cero o 2 hijos con excepción de la Raíz.

árboles
Fig. 10: Podemos apreciar que el árbol de la derecha no esta lleno ya que uno de sus nodos no cumple con la condición cero o 2 hijos. ya que el nodo C solo tiene un hijo.

Árbol binario perfecto: Es un Árbol lleno en donde todos las Hojas están en el mismo Nivel.

árboles
Fig. 11: En la imagen podemos apreciar que el árbol de la izquierda tiene todas sus hojas al mismo nivel y que ademas esta lleno, lo que lo convierte en un árbol binario perfecto. Sin embargo, del lado derecho podemos ver que aunque el árbol esta lleno no tiene todas las hojas al mismo nivel lo que hace que no sea un árbol binario perfecto pero si lleno.


Recorrido sobre Árboles

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden especifico, 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úsqueda en dos tipos, las búsqueda en profundidad y las búsquedas en amplitud.

Búsquedas no informadas

Las búsquedas no informadas son aquellas en que se realiza el viaje por todo el árbol sin tener una pista de donde pueda estar el dato deseado. Este tipo de búsquedas también se conocen como búsquedas a ciegas.

Para comprender mejor que es una búsqueda no informada expondremos el siguiente ejemplo:

Imagine que vamos por la carretera y de repente encontramos dos caminos, el problema a qui es que uno después de 50 kilómetros esta en construcción y el otro nos lleva a nuestro destino, sin embargo ninguno de los caminos tiene señalamiento. Lo que tendríamos que hacer es recorrer el primero camino y después de 50 kilómetros encontrarnos con que el camino esta en construcción, entonces tendríamos que regresar para irnos por el segundo camino,el cual nos lleva a nuestro destino(Para esto ya recorrimos los 50 kilómetros de ida y los 50 kilómetros de regreso lo que nos da 100 kilómetros mas a nuestra ruta).

A este tipo de escenarios en los cuales las búsquedas de hacen a ciegas los conocemos como búsquedas no informadas.

Las siguientes métodos de búsqueda que veremos a continuación(Búsqueda en profundad y Búsqueda en amplitud) pertenecen a  las búsquedas no informadas.

Búsqueda en profundidad

Recorrido Pre-orden: El recorrido inicia en la Raíz y luego se recorre en pre-orden cada unos de los sub-árboles de izquierda a derecha.

Esta definición puede ser un poco compleja de entender por lo que mejor les dejo la siguiente imagen.

árboles
Fig. 12:En la imagen podemos ver el orden en que es recorrido el árbol iniciando desde la Raíz.

árboles
Fig. 13: Codigo de una función recursiva que recorre un árbol en preorden.

Recorrido Pos-orden: Se recorre el pos-orden cada uno de los sub-árboles y al final se recorre la raíz.

Para comprender mejor esta definición observemos la siguiente imagen:

árboles
Fig. 14: En la imagen podemos observar como se realiza el recorrido en Pos-Orden, Sin embargo es importante notar que el primer nodo que se imprime no es la Raiz pues en este recorrido la Raíz de cada Sub-Árbol es procesado al final, ya que toda su descendencia ha sido procesada.
árboles
Fig. 15: Código de una función recursiva que recorre un árbol en posorden

Recorrido in-orden: Se recorre en in-orden el primer sub-árbol, luego se recorre la raíz y al final se recorre en in-orden los demas sub-árboles

árboles
Fig. 16:En la imagen se muestra como es el recorrido In-Orden, 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.

árboles
Fig. 17: Código de una función recursiva que recorre un árbol en inorden

Búsqueda en amplitud.

Se recorre primero la raíz, luego se recorren los demas 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.

Búsqueda en amplitud en árboles
Fig. 18: En la imagen se observa como es que un nodo es buscado mediante la búsqueda en profundidad.

En la imagen podemos observa que el árbol es recorrido en su totalidad pero esto no siempre es a sí, ya que el algoritmo se detiene cuando el elemento buscado es encontrado.

árboles
Fig. 19: Código de un función que recorre el árbol en amplitud.

Si observamos el código de forma minuciosa podemos observar dos puntos muy interesantes, el primero es que esta función no es recursiva, y la segunda es que se utiliza una Cola para controlar el flujo del recorrido.

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

Conclusiones

Como hemos observado los arboles son estructuras bastante complejas, tiene una gran aplicaciones en la ciencia y en la programación convencional. En los últimos años este tipo de estructuras ha sido utilizadas con mucha frecuencia en la Inteligencia artificial.

En esta publicación hemos visto los puntos vas relevantes a en cuenta a lo que son los arboles y los principales métodos de búsqueda, sin embargo estamos lejos de cubrir este tema en profundidad ya que existen muchísimos tipos de operaciones y algoritmos que se pueden realizar sobre estas estructuras de datos.

Espero que este información te sirve de utilidad y no olvides darle like y recomendar esta publicación ya que esto me servirá para crear mas y mejor material.

Artículos relacionados

Estructuras de datos – Listas ligadas Sin duda una de las partes mas emocionantes cuando programamos es la parte de la algoritmia donde tenemos que usar la mente para resolver problemas qu...
Pila (Stack) En días pasados hablamos acerca de las Colas o Queue las cuales siguen la filosofía FIFO (First In - First Out) o Primero en entrar - Primero en salir...
Estructura de datos – Queue (Cola) En esta entrada quiero platicarles de las Colas (Queue) un tipo de estructura de datos muy utilizada. ¿Pero que es exactamente una colas?, Cuando digo...

Oscar Blancarte

Ideológico, Innovador y emprendedor, Padre, Tecnólogo y Autor, amante de la ciencia y la tecnología en todos sus colores y sabores. Arquitecto de software & Full Stack Developer con experiencia en la industria del desarrollo de software y la consultoría. Amante de la programación y el Ajedrez.

Un comentario en “Estructura de datos – Árboles

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *