Was sind die Anwendungen von Rosenbäumen?

Ich habe kürzlich etwas über die Datenstruktur des Rosenbaums dataerfahren , aber wenn ich nur von einer Haskell- Definition und der winzigen Wikipedia-Beschreibung abkomme, habe ich einige Probleme zu verstehen, welche Anwendungen ein Rosenbaum haben könnte.

Als Referenz die Haskell- dataDefinition:

data RoseTree a = RoseTree a [RoseTree a]

Für diejenigen, die mit Haskell nicht vertraut sind - es handelt sich um eine rekursive Datentypdefinition mit einem beliebigen Typ a, bei der dem Typkonstruktor ein Literal des Typs agefolgt von einer optional leeren Liste des Typs RoseTreedesselben Typs bereitgestellt wird a.

Wie ich es sehe:

• Diese Datenstruktur ist standardmäßig ungeordnet (obwohl ich davon ausgehe, dass die meisten praktischen Anwendungen eine Reihenfolge für die Suche implementieren).

• Die Datenstruktur erzwingt zu keinem Zeitpunkt eine feste Anzahl von Knoten pro Schicht, mit Ausnahme der globalen Wurzel, die einen einzelnen Knoten haben muss

Angesichts dieser minimalen Menge an Informationen habe ich Probleme herauszufinden, wann man diesen Baumtyp verwenden könnte.

Wie wird zusätzlich zu der Frage im Titel, ob die Suche tatsächlich in den meisten Anwendungen eines Rosenbaums implementiert ist, dies getan?

Sie scheinen eine übermäßig "Denkweise für Datenstrukturen und Algorithmen" zu haben. Nicht jeder Baum ist eine Art Suchbaum. Datenstrukturen sind häufig so konzipiert, dass sie Aspekten eines Domänenmodells entsprechen oder diese erfassen.

S-Ausdrücke sind fast genau Rosenbäume. (Oder besser gesagt, ich würde sagen, dass sie normalerweise als Rosenbäume betrachtet werden. Wikipedia sagt zu Recht, dass sie eher binären Bäumen ähneln, aber was man als "richtige" S-Ausdrücke bezeichnen könnte, unterscheidet sich nur geringfügig von Rosenbäumen.) In jedem Fall können Sie sie als generische Darstellung für einen abstrakten Syntaxbaum verwenden. Dies hat den Vorteil, dass Sie leicht generische Operationen schreiben können, z. B. "Alle Variablen finden" oder "Parameter austauschen" oder "Dieses Symbol umbenennen". Es ist auch insofern erweiterbar, als das Hinzufügen eines neuen Knotentyps zu Ihrer abstrakten Syntax häufig keine wirklichen Änderungen erfordert. Die Nachteile sind, dass es eigentlich keine Einschränkungen gibt, so dass Sie nicht a priori daran gehindert werden, Unsinn zu schreiben. Dies kann für Benutzer durch standardmäßige abstrakte Datentyptechniken gemindert werden, aber der Implementierer von Transformationen und dergleichen muss sich mit der unstrukturierten Darstellung befassen, obwohl er "weiß", dass die Eingabe über eine Datentypinvariante strukturiert ist. Wenn diese Gewissheit fehl am Platz ist (möglicherweise weil sich die Dinge geändert haben), sind die Fehler natürlich unvorhersehbar und schwer zu debuggen.

In der Praxis wird das Data.TreeModul in den Standardbibliotheken zwar von einem Rosenbaum bereitgestellt, in der Haskell-Community jedoch von fast niemandem verwendet. Das Definieren von benutzerdefinierten Datentypen, die die Einschränkungen explizit erfassen, ist so einfach, dass es kaum einen Grund gibt, einen generischen Bibliothekstyp zu verwenden. Darüber hinaus wurde eine enorme Menge an Forschung und Praxis in Bezug auf die Durchführung generischer Operationen über benutzerdefinierte Typen durchgeführt, wodurch viele der Vorteile der Verwendung einer generischen Darstellung entfallen. Schließlich neigen Haskeller dazu, explizite, erzwungene Beschränkungen zu befürworten, und sind bereit, dafür zu zahlen.

Um Ihre letzte Frage zu beantworten, ist die Suche nach einem AST oft unwichtig und / oder es wird allgemein angenommen, dass die ASTs klein genug sind, um nur das Ganze laufen zu können. Zugegebenermaßen ist es nicht ungewöhnlich, Definitionen in einer separaten Datenstruktur mit Verweisen auf den AST zu sammeln, die als eine Art Index angesehen werden könnten. In ähnlicher Weise werden bei einigen Optimierungsdurchläufen (normalerweise lokal und vorübergehend) Indizes erstellt, um deren Betrieb zu vereinfachen und zu beschleunigen. Die Struktur des AST entspricht dem Eingang und kann daher nicht "neu ausbalanciert" werden. Daher ist es ungewöhnlich, dass der AST selbst Indexinformationen oder Informationen zur "Suche" enthält.