El árbol es una de las estructuras de datos más importantes de la informática, y su nombre proviene de una analogía visual —no de una relación con la botánica—: al representarse gráficamente, sus elementos se despliegan a partir de un punto de origen de forma similar a las ramas de un árbol o a un árbol genealógico, con el que comparte buena parte de su terminología (raíz, hijos, hermanos, hojas).
Anatomía de un árbol
- Raíz: el nodo superior del árbol, del que parten todos los demás.
- Nodo: cada elemento del árbol, que puede tener nodos «hijos» conectados hacia abajo.
- Hoja: un nodo sin hijos, situado en el extremo final de una rama.
- Subárbol: cualquier nodo, junto con todos sus descendientes, puede considerarse a su vez un árbol completo por derecho propio —una propiedad que hace de los árboles una estructura naturalmente recursiva, tanto en su definición como en los algoritmos que operan sobre ellos.
Por qué son tan usados
Los árboles permiten organizar información de forma jerárquica y, en muchas de sus variantes, realizar búsquedas mucho más eficientes que en una simple lista: en un árbol binario de búsqueda bien equilibrado, localizar un elemento entre un millón de datos puede requerir tan solo unas veinte comparaciones, en lugar de recorrer, en el peor caso, la lista entera.
Variantes más conocidas
- Árbol binario: cada nodo tiene como máximo dos hijos, habitualmente distinguidos como «izquierdo» y «derecho».
- Árbol binario de búsqueda: un árbol binario en el que los valores se organizan según una regla de orden, lo que permite búsquedas, inserciones y eliminaciones eficientes.
- Árbol B: diseñado específicamente para minimizar los accesos a disco, es la estructura que sostiene el funcionamiento de la mayoría de los sistemas de bases de datos y de archivos actuales.
Presencia cotidiana, aunque invisible
Aunque rara vez se perciben como tales, los árboles están detrás de estructuras que cualquier usuario de un ordenador maneja a diario: el propio sistema de carpetas y subcarpetas de un ordenador es, estructuralmente, un árbol, y lo mismo ocurre con la estructura de etiquetas anidadas de un documento HTML o con los índices que emplean las bases de datos para acelerar sus consultas.
En este sitio