Árboles k-arios (m-arios o n-arios)

¿Qué es un Árbol K-ario?

Un árbol k-ario (también conocido como árbol n-ario o m-ario, dependiendo de la notación) es una estructura de datos en la que cada nodo puede tener hasta k hijos.

Definición Formal

Un árbol k-ario es un árbol en el que:

• Cada nodo puede tener entre 0 y k hijos.
• Si un nodo tiene más de k hijos, ya no cumple con la definición de árbol k-ario.

Representación

Para implementar un árbol k-ario, los nodos se pueden representar mediante:

• Un valor almacenado (de tipo genérico, como int, String, etc.).
• Una estructura para almacenar referencias a los hijos del nodo, típicamente un array o una lista.

class KaryTree<T> {
    private KaryTreeNode<T> root; // Nodo raíz del árbol
    private int k; // Número máximo de hijos por nodo
}

// Clase para representar un nodo del árbol k-ario
class KaryTreeNode<T> {
    T value; // Valor almacenado en el nodo
    List<KaryTreeNode<T>> children; // Lista de hijos del nodo
}        

Problema de representarlos como arrays

El problema de representar los hijos de cada nodo como arrays son los siguientes:

• Puede provocar problemas de optimización
• Cuando rara vez los arrays de cada nodo son rellenados
• Se gasta espacio de almacenamiento que no se usa

Problemas de Representación

1. Uso de Arrays: Si se utiliza un array para almacenar los hijos:
   • Es eficiente cuando el árbol está lleno, ya que los arrays tienen acceso directo por índice.
   • Consume más memoria cuando los nodos tienen menos de k hijos, debido al espacio reservado para referencias vacías.

Para optimizar el uso de memoria y que los árboles estén completos para no desperdiciar memoria tiene que ver con el tipo de árbol que sea, si se trata de alguno de estos es mejor la implementación con el uso de arrays.

Operaciones en Árboles K-arios

1. Inserción:
   • No hay reglas específicas para determinar dónde insertar un nuevo nodo.
   • Puede ser arbitrario o definido por las necesidades del problema.
2. Eliminación:
   • Similar a la inserción, depende de las reglas del árbol y del propósito.
3. Recorrido:
   • Recorrido en profundidad: Visita los nodos explorando lo más profundo posible antes de retroceder.
   • Recorrido en anchura: Visita los nodos nivel por nivel.
4. Búsqueda:
   • Localización de un nodo específico utilizando algoritmos de búsqueda en profundidad o en anchura.

---

Aplicaciones de los Árboles K-arios

1. Sistemas de Archivos y Bases de Datos:
   • Los árboles B y B+ son ejemplos de árboles k-arios utilizados para indexar y buscar información eficientemente.
   • Permiten gestionar un número elevado de hijos en nodos, reduciendo la cantidad de accesos al disco.
2. Resolución de Problemas en Inteligencia Artificial:
   • Representación de estados en sistemas multiestado (por ejemplo, juegos como el tres en raya).
   • Cada nodo representa un estado, y los hijos representan transiciones a nuevos estados.
3. Algoritmos de Búsqueda y Decisión:
   • Algoritmos de búsqueda tanto en profundidad como en anchura.
   • Backtracking: dado un problema, considerar todas las posibles combinaciones y optimizar el árbol de búsqueda para encontrar la solución óptima.
   • Utilizados en juegos para tomar decisiones óptimas considerando las posibles respuestas del oponente.

---

Ejemplo Práctico

Árbol de Estados en un Juego

Consideremos el juego del tres en raya:

• El estado inicial (tablero vacío) tiene hasta 9 hijos (una ficha en cada posición).
• Cada estado hijo representa un tablero actualizado con una jugada.
• Este árbol permite aplicar algoritmos como búsqueda en profundidad o minimax para encontrar la mejor jugada.