Se define un árbol como: “Una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol está vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como subárboles. Las raíces de los subárboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus subárboles.” según (Universidad de Chile, s.f.).
Por otra parte, (Ing. Blancarte, 2014) menciona que “Los Árboles son las estructuras de datos más utilizadas, pero también una de las más complejas, los Árboles se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal como las Listas Enlazadas, Colas, Pilas, entre otros.”
Según Joyanes (2007) ha mencionado que “Los árboles se utilizan para representar fórmulas algebraicas, para organizar objetos en orden de tal forma que las búsquedas son muy eficientes, y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles. Además de las aplicaciones citadas, los árboles se utilizan en diseño de compiladores, proceso de texto y algoritmos de búsqueda.”
Según las fuentes podemos constatar que los arboles son estructuras de datos importantes en los sistemas computacionales y es menester que entendemos como futuros programadores para tomar decisiones óptimas para nuestros programas, no es una cuestión de gusto, sino que es necesario siempre analizar las posibilidades y escoger la que beneficie nuestro programa y nuestros computadores. En la Figura 1 se logra ver la representación de un árbol.
Figura 1
Características:
Joyanes (2007) menciona que “Un árbol consta de un conjunto finito de elementos, denominados nodos y un conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo.”
En el momento que el árbol no posea la característica de estar vacío, el primer nodo en ser insertado será llamado raíz, dado a que viene a ser el dato inicial del árbol.
Un nodo puede ser considerado como padre si tiene nodos sucesores. Estos nodos sucesores se llaman hijos. Los nodos que no poseen hijos vienen a ser los extremos de él árbol, por ello es que como en los arboles de la naturaleza, a estos nodos se les llama hojas.
En 2011, Departamento de Informática Universidad de Valladolid menciona que “un camino en un árbol como cualquier secuencia de nodos del árbol, n1 ... np, que cumpla que cada nodo es padre del siguiente en la secuencia (es decir, que ni es el padre de ni+1). La longitud del camino se define como el número de nodos de la secuencia menos uno (p-1).”
Por otra parte, si abstraemos lo suficiente podríamos dar con la conclusión que la altura de un nodo en un árbol como la longitud del camino más largo que comienza en el nodo y termina en una hoja, lo mismo que se hace cuando se mide un árbol de la naturaleza, se cuenta hasta la hoja más alta.
Notas:
- La altura de un nodo hoja es 0.
- La altura de un nodo es igual a la mayor altura de sus hijos + 1
- La altura de un árbol se define como la altura de la raíz.
Se define la profundidad de un nodo en un árbol como la longitud del camino (único) que comienza en la raíz y termina en el nodo. También se denomina nivel. Se pueden apreciar los niveles en la figura 2.
Figura 2
Recorrido de árboles:
Pasar a través de los elementos de un árbol por medio de las conexiones entre padres e hijos se llama recorrer el árbol, y la acción es un camino por el árbol. A menudo, una operación puede ser realizada cuando un puntero llega a un nodo en particular. Un camino en el que cada nodo padre es atravesado antes que sus hijos se llama camino de pre-orden; un camino en el que los hijos son atravesadas antes que sus respectivos padres se llaman un camino de post-orden un camino en el que el subárbol izquierdo de un nodo, el nodo en sí, y finalmente su subárbol derecho son atravesadas se llama un inorden. (Esta última situación, en referencia a exactamente dos subárboles, un subárbol izquierdo y un subárbol derecho, es específicamente un árbol binario.)
Se puede apreciar el recorrido en la Figura 3.
Figura 3
El movimiento a través de árboles, salvo que implementemos punteros al nodo padre, será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo.
En general, intentaremos que exista algún significado asociado a cada uno de los punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qué serlo. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directorio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios.
Referencias:
- Universidad de Chile. (s.f.). CC30A Algoritmos y Estructuras de Datos: Estructuras de datos básicas. Recuperado 1 junio, 2019, de https://users.dcc.uchile.cl/%7Ebebustos/apuntes/cc30a/Estructuras/
- Blancarte, O. J. B. I. Ing. (2014, 22 agosto). Estructura de datos - Árboles - Oscar Blancarte - Software Architecture. Recuperado 1 junio, 2019, de https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
- Joyanes Aguilar, L., Sánchez García, L., & Zahonero Martínez, I. (2007). Estructura de datos en C++. McGraw-Hill.
- Departamento de Informática Universidad de Valladolid. (2011). Estructuras de Datos y Algoritmos Tema 4: Árboles. Recuperado 2 junio, 2019, de https://www.infor.uva.es/~cvaca/asigs/doceda/tema4.pdf