Nicht mutierende Implementierung eines Array-Baums

[Borgenta]

Moin, ich stehe gerade vor einem Problem bei einer zu lösenden Aufgabe.

Und zwar ist die Ausgangslage ein Arraybaum, in den ich etwas hinzufügen/verändern soll. An sich nicht weiter problematisch. Mein Problem ist, dass das Ganze nicht mutierend passieren soll.

Hier habe ich nun weniger ein Programmierungsproblem als vielmehr ein Verständnisproblem. Ich will doch etwas in diesen bestehenden Baum einpflegen, wie soll ich das anstellen, ohne den Baum zu verändern? Womöglich verstehe ich etwas an der Aufgabe falsch.

Ich hoffe, man weiß was ich meine und irgendwer kann mir einen Denkanstoß geben. Da steige ich nämlich leider nicht durch.

Eine Funktion zum Suchen eines Wert im Baum sowie eine mutierende Funktion zum Hinzufügen/Ändern eines Werts habe ich, aber weiter komme ich leider nicht.

Besten Dank für die Hilfe!

[__deets__]

Das ist Gang und gäbe in funktionalen Sprachen, die erlauben keine Veränderungen. Das Vorgehen besteht dann in der Erstellungen einer Kopie, die an der entsprechenden Stelle verändert ist. Dazu kommen üblicherweise rekursive Funktionen zum Einsatz, die den Baum traversieren, und ein oder mehrere Argumente mit Funktionen die zb eine gewünschten knoten erkennen, und den dann modifiziert (oder entfernt) zurück geben. Also ziemlich genau was du schon hast.

[__blackjack__]

@Borgenta: Ändere „Ich will doch etwas in einen bestehenden Baum einpflegen“ zu „Ich will einen neuen Baum mit dem/den zusätzlichen oder geänderten Wert(en)“. Dabei darf man ruhig unveränderte Teile der Datenstruktur auch in den neuen Baum übernehmen.

[Borgenta]

Also sehe ich es richtig, dass ich da, einfach weil es begrifflich schon ein Widerspruch ist, nichts dran verändere, sondern das Ding kopiere und an dem kopierten Stück dann meine Änderungen vornehme und diese Kopie an die Stelle des Originals setze? Und wenn ich den nächsten Wert nehme, kopiere ich meine Kopie und setze die an die Stelle der ursprünglichen Kopie?

Vielen Dank für die Antworten!

[__deets__]

Jup. Wer nicht mutiert, kopiert.

[snafu]

Wahrscheinlich meinst du das schon mit Ersetzen, aber es geht halt um die Rückgabe eines neuen veränderten Baums (wie du an sich auch schon erkannt hast). Quasi so:

Code: Alles auswählen

tree = add_node(tree, node)