¿Cuáles son las aplicaciones generales de los árboles en estructuras de datos y algoritmos? Por qué

Sin mencionar las estructuras de datos, la naturaleza recursiva de los árboles, la estructura de descripción más común de las computadoras, la atraviesa. El árbol quadtree del diccionario de búsqueda de árboles es la aplicación práctica de los árboles. Es solo que los árboles no describen las estructuras de baja dimensión (de hecho, las estructuras unidimensionales también pueden considerarse árboles degenerados).

A nivel de algoritmo, los árboles están básicamente en todas partes (por supuesto, a veces ocultos). Las instrucciones ejecutadas por la computadora son lineales y el código del programa es secuencial y unidimensional. Una vez que es necesario resolver problemas de alta dimensión, los árboles solo pueden usarse para describir la lógica de alta dimensión y servir como puente.

Un ejemplo de este algoritmo es el siguiente.

Categorías de recorrido del espacio de estados: DFS, BFS

Categorías de toma de decisiones: varios autómatas (especialmente KMP degenerado a un bit), codicioso, divide y vencerás, programación dinámica (todas pertenecen a espacio de estados Traverse) y hacer coincidir.

Gráficos y flujos: búsqueda de rutas (ruta más corta) y árboles de expansión

Hay muchos más ejemplos de aplicaciones, como XML, árboles DOM, reconocimiento de patrones y árboles de sintaxis en compiladores Aplicación, JSON transmisión de datos, estructura de rutas de disco, etc...

La universalidad de los árboles depende de la coherencia de su estructura con algoritmos comunes de resolución de problemas y de su estructura simple y rigurosa: definición recursiva, orden topológico (sin bucles) y sencillo de implementar. Cuando se enfrentan a estados de alta dimensión, es casi seguro que otras estructuras no son tan simples como convertirse en árboles, convirtiéndose así en un puente entre la implementación unidimensional de la organización y la lógica de alta dimensión.