1. INTRODUCCIÓN A LOS ÁRBOLES COMPUTACIONALES
Definición y estructura básica de un árbol
Definición: Un árbol binario es una estructura de datos que relaciona información de manera jerárquica no lineal. Por ello, justamente recibe el nombre de árbol por la manera como se presenta la información. La información se estructura de forma ramificada como si fuera un árbol. Adicionalmente, es binario porque únicamente se desprenden dos ramas.
Estructura:
Raíz: La raíz es el primer subconjunto y solo contiene un elemento.
Subárbol izquierdo: Representa un segundo subconjunto y es igualmente un árbol binario. Se le reconoce como subárbol izquierdo del árbol original.
Subárbol derecho: El tercer subconjunto es también un árbol binario y es conocido como el subárbol derecho del árbol original
Propiedades y características de los árboles binarios
Características:
• Un árbol binario puede tener solo un nodo raíz.
• Un árbol binario en el que no existe ningún nodo se denomina un árbol nulo.
• Un árbol binario puede tener cero, uno o dos sub árboles desde cualquier nodo del árbol.
2. CLASIFICACIÓN DE LOS ÁRBOLES
Familias principales de árboles: árboles binarios, árboles de expansión y árboles de decisión
Ejemplos de aplicaciones de cada tipo de árbol en la computación:
Árboles binarios: es una estructura de datos no lineal en la que cada nodo puede apuntar a uno o máximo a dos nodos.
Árboles de expansión: es un árbol compuesto por todos los vértices y algunas (quizá todas) de las aristas.
Árboles de discusión: son un modelo de aprendizaje automático que se utiliza para tomar decisiones basadas en condiciones específicas. Se representan como un árbol donde cada nodo interno representa una característica, cada rama representa un resultado de la prueba de esa característica, y cada hoja representa un resultado de clasificación
3. CONCEPTOS CLAVE
Árboles binarios de búsqueda (BST): Se utilizan para implementar estructuras de datos como los árboles AVL y los árboles rojo-negro, que permiten realizar búsquedas eficientes, inserciones y eliminaciones en tiempo logarítmico.
Árboles de expansión mínima (MST): Son una herramienta fundamental en la computación, especialmente en algoritmos como el algoritmo de Kruskal y el algoritmo de Prim, que se utilizan para encontrar el árbol de expansión mínima en un grafo ponderado.
Árboles de decisión en inteligencia artificial y aprendizaje automático: Son un método popular en inteligencia artificial y aprendizaje automático para la clasificación y la regresión. Un ejemplo típico es el uso de árboles de decisión para predecir si un cliente va a comprar un producto en línea o no, basándose en diferentes características como la edad, el género, el historial de compras, etc. El árbol de decisión se construye mediante algoritmos que buscan dividir el conjunto de datos en subconjuntos
4. APLICACIÓN PRÁCTICA
Resolución de problemas del entorno real utilizando árboles computacionales
Árbol de clasificación de la biología:
Fig. 1 Árbol Taxonomía de
Animales (Runestone, 2021)
Arbol de jerarquía de un sistema de archivos en Unix:
Fig. 2 Árbol jerarquía de un
sistema de archivos en Unix (Runestone, 2021)
Formulación de problemas utilizando tipos específicos de árboles
1. Árbol de decisión en la clasificación de enfermedades:
Problema: Un hospital quiere desarrollar un sistema de apoyo para diagnosticar enfermedades basado en síntomas observados en los pacientes.
Solución: Utilizar un árbol de decisión donde cada nodo interno representa una pregunta sobre un síntoma específico y cada hoja representa un diagnóstico final. Los médicos pueden seguir el árbol de decisión para llegar a un diagnóstico basado en los síntomas presentados por el paciente.
2. Árbol de búsqueda en algoritmos de búsqueda binaria:
Problema: Se necesita buscar eficientemente un elemento en una lista ordenada.
Solución: Utilizar un árbol de búsqueda binaria donde los elementos de la lista se organizan en un árbol de tal manera que se pueda realizar una búsqueda binaria. Cada nodo del árbol contiene un elemento de la lista y tiene dos hijos, uno para los elementos menores y otro para los elementos mayores. Esto permite una búsqueda eficiente en tiempo logarítmico.
Ejercicios prácticos para diseñar y resolver problemas utilizando árboles de decisión
1. Clasificación de especies de plantas:
Problema: Un botánico quiere clasificar diferentes especies de plantas basadas en características como la forma de las hojas, el color de las flores y la altura de la planta.
Solución: Diseñar un árbol de decisión donde cada nodo interno representa una pregunta sobre una característica específica de la planta, como "¿Son las hojas largas o cortas?" o "¿Son las flores rojas o amarillas?". Cada hoja del árbol representa una especie de planta identificada. El botánico puede seguir el árbol de decisión para clasificar una planta desconocida en una especie específica.
2. Diagnóstico de enfermedades en animales:
Problema: Un veterinario necesita diagnosticar enfermedades en animales domésticos basadas en síntomas observados, como temperatura corporal, comportamiento y síntomas físicos.
Solución: Construir un árbol de decisión donde cada nodo interno representa una pregunta sobre un síntoma específico, como "¿Tiene fiebre el animal?" o "¿Está vomitando?". Cada hoja del árbol representa un diagnóstico final, como "resfriado" o "intoxicación alimentaria". El veterinario puede seguir el árbol de decisión para diagnosticar la enfermedad del animal.
5. IMPLEMENTACIÓN DE ALGORITMOS
Algoritmos para encontrar árboles binarios de búsqueda y de expansión mínima como el algoritmo de Kruskal o el algoritmo de Prim
Arboles binarios de búsqueda: Un árbol binario de búsqueda es una estructura de datos en la que cada nodo tiene como máximo dos hijos, y los valores en el subárbol izquierdo son menores que el valor del nodo, mientras que los valores en el subárbol derecho son mayores que el valor del nodo.
Arboles expansión mínima: Los árboles de expansión mínima son subgrafos de un grafo conectado que contienen todos los vértices del grafo original y la menor cantidad posible de aristas, de modo que no haya ciclos y la suma de los pesos de las aristas sea mínima.
Ejemplos de implementación en diferentes lenguajes de programación
Árbol Binario de Búsqueda en Java
