Hace poco me enteré de la estructura de datos del árbol de rosas, pero simplemente saliendo de una datadefinición de Haskell y la pequeña descripción de Wikipedia , tengo algunos problemas para entender qué aplicaciones podría tener un árbol de rosas.
Como referencia, la datadefinición de Haskell :
data RoseTree a = RoseTree a [RoseTree a]
Para aquellos que no están familiarizados con Haskell, es una definición de tipo de datos recursiva con un tipo arbitrario a, donde el constructor de tipos se proporciona con un literal de tipo aseguido de una lista de tipos opcionalmente vacía RoseTreeen el mismo tipo a.
La manera en que lo veo:
Esta estructura de datos está desordenada de manera predeterminada (aunque supongo que la mayoría de las aplicaciones prácticas implementan alguna forma de ordenar para buscar)
La estructura de datos no impone un número fijo de nodos por capa en ningún punto, excepto la raíz global, que debe tener un solo nodo
Dada esa cantidad mínima de información, tengo problemas para determinar cuándo se podría usar este tipo de árbol.
Además de la pregunta en el título, si la búsqueda se implementa en la mayoría de las aplicaciones de un árbol de rosas, ¿cómo se hace?
Respuestas:
Parece tener una mentalidad excesivamente "estructura de datos y algoritmos". No todos los árboles son algún tipo de árbol de búsqueda. Las estructuras de datos a menudo están diseñadas para corresponder o capturar aspectos de un modelo de dominio.
Las expresiones S son casi exactamente rosales. (O, mejor dicho, diría que normalmente se los considera rosales. Wikipedia tiene razón al decir que son más como árboles binarios, pero lo que podríamos llamar expresiones S "adecuadas" son solo ligeramente diferentes de los rosales). En cualquier caso, puede usarlos como una representación genérica para un árbol de sintaxis abstracta. La ventaja de hacerlo es que puede escribir fácilmente operaciones genéricas, por ejemplo, "buscar todas las variables" o "cambiar parámetros" o "cambiar el nombre de este símbolo". También es extensible porque agregar un nuevo tipo de nodo a su sintaxis abstracta a menudo no requiere realmente cambiar nada. Las desventajas son que en realidad no hay restricciones, por lo que a priori no le impide escribir tonterías. Esto puede mitigarse para los usuarios mediante técnicas estándar de tipo de datos abstractos, pero el implementador de transformaciones y tales debe lidiar con la representación no estructurada a pesar de que "saben" que la entrada está estructurada a través de un tipo de datos invariante. Por supuesto, cuando esa certeza está fuera de lugar (posiblemente porque las cosas han cambiado), los errores tienden a ser impredecibles y difíciles de depurar.
En la práctica, aunque el
Data.Treemódulo en las bibliotecas estándar proporciona un rosal, casi nadie lo usa en la comunidad de Haskell. Definir tipos de datos personalizados que capturan explícitamente las restricciones es tan fácil que hay pocas razones para usar un tipo de biblioteca genérico. Además, ha habido una enorme cantidad de investigación y práctica en torno a la realización de operaciones genéricas sobre tipos personalizados que elimina muchos de los beneficios de utilizar una representación genérica. Finalmente, los Haskellers tienden a estar muy a favor de las restricciones explícitas y forzadas y están dispuestos a pagar para obtenerlo.Para responder a su última pregunta, a menudo buscar un AST no es importante y / o se supone que los AST son lo suficientemente pequeños como para que caminar solo sea aceptable. Es cierto que no es raro recopilar definiciones en una estructura de datos separada con referencias en el AST que podrían verse como una especie de índice. Del mismo modo, algunos pases de optimización (generalmente a nivel local y temporal) crearán índices para simplificar y acelerar su operación. La estructura del AST corresponde a la entrada y, por lo tanto, no se puede "reequilibrar" ni nada de eso. Como tal, es poco común que el AST contenga información de indexación o información para ayudar a "buscar".
fuente