Wie ersetze ich einen Teil eines Baums durch einen anderen Baum am angegebenen Index?
Angenommen, ich habe zwei Bäume:
Baum A -
'(+ (* 5 6) (sqrt 3)):
Baum B -
'(- 4 2):
Ziel: Ersetzen Sie einen der Teilbäume von Baum A durch Baum B an einer bestimmten Indexposition von Baum A. Die Indexposition beginnt am Wurzelknoten bei 0 und steht an erster Stelle. In der Abbildung für Baum A oben habe ich alle Knoten mit ihrem Index gekennzeichnet, um dies zu zeigen.
Ersetzt beispielsweise (replace-subtree treeA 4 treeB)den Teilbaum bei Index 4 in Baum A durch Baum B, was zu folgendem Baum führt (+ (* 5 6) (- 4 2)):
Wie implementiere ich (replace-subtree treeA index treeB)?
Diese Frage hat etwas mit meiner anderen Frage zu tun : Wie erhalte ich einen Teilbaum nach Index? . Ich hatte große Schwierigkeiten, es zu lösen, fand aber schließlich eine praktikable Lösung für dieses Problem, indem ich den Continuation-Passing-Stil (CPS) verwendete. Dieses Problem scheint hier jedoch weitaus schwieriger zu sein. Ich bin völlig ratlos, wie ich überhaupt anfangen soll! Implementierungen und Hinweise sind herzlich willkommen. Ich würde mich besonders für Implementierungen interessieren, die nicht verwendet werden call/cc.
BEARBEITEN
Während ich auf Antworten wartete, kam ich auf eine Notlösung. Es hängt davon ab set!, was ich nicht bevorzuge.
(define (replace-subtree tree index replacement)
(define counter 0)
(define replaced #f) ; Whether or not something has been replaced.
(define (out-of-bounds-error)
(error "Index out of bounds" index))
(define (traverse-tree tree)
(cond [(null? tree)
(error "Invalid tree: ()")]
[(= counter index)
(set! counter (+ counter 1))
(set! replaced #t)
replacement]
[(pair? tree)
(set! counter (+ counter 1))
(cons (car tree)
(traverse-children (cdr tree)))]
[else
;; Possible only during the initial call to traverse-tree.
;; e.g. (replace-subtree 'not-a-list 9999 '(+ 1 2)) -> error.
(out-of-bounds-error)]))
(define (traverse-children children)
(cond [(null? children) '()]
[(list? (car children))
;; list? instead of pair? to let traverse-tree handle invalid tree ().
(cons (traverse-tree (car children))
(traverse-children (cdr children)))]
[(= counter index)
(set! counter (+ counter 1))
(set! replaced #t)
(cons replacement
(traverse-children (cdr children)))]
[else
(set! counter (+ counter 1))
(cons (car children)
(traverse-children (cdr children)))]))
(let ([result (traverse-tree tree)])
(if replaced
result
(out-of-bounds-error))))
Antworten
Dies ist ein schwierigeres Problem als ich erwartet hatte. Ein Grund, warum es schwierig ist, ist, dass die Dinge, die Sie "Bäume" nennen, eigentlich keine Bäume sind: Sie sind DAGs (gerichtete azyklische Diagramme), weil sie Teilbäume gemeinsam nutzen können. Einfach gesagt passiert dies nur für Blattknoten: In (a b b)den Knoten mit Index 1 und 2 sind eq?: sie sind das gleiche Objekt. Tatsächlich kann es jedoch für jeden Knoten passieren: gegeben
(define not-a-tree
(let ([subtree '(x y)])
(list 'root subtree subtree)))
Die Knoten mit Index 1 und 2 sind dasselbe Objekt und keine Blattknoten: Dies ist eine DAG, kein Baum.
Dies ist wichtig, weil es einen offensichtlichen Ansatz entgleist:
- Suchen Sie den Knoten mit dem Index, an dem Sie interessiert sind.
- Gehen Sie über den Baum und erstellen Sie einen neuen Baum, bis Sie diesen Knoten mithilfe
eq?von Knoten finden. Ersetzen Sie ihn dann.
Sie können sehen, dass dies fehlschlagen würde, wenn ich den Knoten durch Index 2 ersetzen wollte (x y y): Es würde stattdessen den Knoten durch Index 1 ersetzen.
Ein Ansatz , der wahrscheinlich ist dann die einfachste ist es, diese ‚Bäume‘ zu nehmen und sie in Bäume , in denen Knoten keine Identität haben. Führen Sie dann den Austausch für diese Bäume wie oben beschrieben durch und konvertieren Sie sie dann zurück in die ursprüngliche Darstellung. Dies verliert jedoch möglicherweise eine wichtige Struktur: Das obige Objekt wird beispielsweise von einer DAG in einen Baum umgewandelt. In der Praxis ist das unwahrscheinlich.
Dazu benötigen Sie eine Funktion, um die alten Bäume zu übernehmen, sie in neue Bäume mit geeigneter Einzigartigkeit umzuwandeln und sie dann wieder umzuwandeln. Dies ist mit ziemlicher Sicherheit der konzeptionell einfachste Ansatz, aber ich war zu faul, um den ganzen Code zu schreiben.
Hier ist eine Antwort, die nicht dieser Ansatz ist. Stattdessen müssen Sie über den Baum gehen und dabei den Knotenindex verfolgen und bei Bedarf einen neuen Baum erstellen. Um dies zu tun, muss das Ding, das in einen Knoten gelangt, zwei Dinge zurückgeben: einen Knoten (der ein neu erstellter Knoten sein kann, dh der Ersatzknoten oder der ursprüngliche Knoten, an den er übergeben wurde) und den neuen Wert des Index. Dies geschieht, indem zwei Werte vom Walker zurückgegeben werden, und dabei gibt es eine ganze Menge Haare.
Dies versucht auch nicht, eine kleine Teilmenge von Racket zu verwenden: Es werden mehrere Werte verwendet, einschließlich syntax ( let-values), wodurch die Verwendung weniger schmerzhaft wird, und es wird auch for/foldder größte Teil der Arbeit erledigt , einschließlich des Faltens mehrerer Werte. Sie müssen diese Dinge also verstehen, um zu sehen, was sie bewirken. (Es bedeutet wahrscheinlich auch, dass es nicht für eine Antwort auf Hausaufgaben geeignet ist.)
Eine erwähnenswerte Sache ist, dass der Walker ein bisschen schummelt: Sobald der Austausch abgeschlossen ist, versucht er nicht einmal, den Index richtig zu berechnen: Er weiß nur, dass er größer ist, als er interessiert, und fällt aus.
Hier sind zunächst Abstraktionen für den Umgang mit Bäumen: Beachten Sie, dass dies make-nodenicht ganz mit der make-nodeAntwort auf die vorherige Frage übereinstimmt: Es wird jetzt eine Liste von Kindern gewünscht, die eine viel nützlichere Signatur darstellt.
(define (make-node value children)
;; make a tree node with value and children
(if (null? children)
value
(cons value children)))
(define (node-value node)
;; the value of a node
(cond
[(cons? node)
(car node)]
[else
node]))
(define (node-children node)
;; the children of a node as a list.
(cond
[(cons? node)
(cdr node)]
[else
'()]))
Hier ist die Funktion, die die Arbeit erledigt.
(define (replace-indexed-subtree tree index replacement)
;; Replace the subtree of tree with index by replacement.
;; If index is greater than the largest index in the tree
;; no replacemwnt will happen but this is not an error.
(define (walk/indexed node idx)
;; Walk a node with idx.
;; if idx is less than or equal to index it is the index
;; of the node. If it is greater than index then we're not
;; keeping count any more (as were no longer walking into the node).
;; Return two values: a node and a new index.
(cond
[(< idx index)
;; I still haven't found what I'm looking for (sorry)
;; so walk into the node keeping track of the index.
;; This is just a bit fiddly.
(for/fold ([children '()]
[i (+ idx 1)]
#:result (values (if (< i index)
node
(make-node (node-value node)
(reverse children)))
i))
([child (in-list (node-children node))])
(let-values ([(c j) (walk/indexed child i)])
(values (cons c children) j)))]
[(= idx index)
;; I have found what I'm looking for: return the replacement
;; node and a number greater than index
(values replacement (+ idx 1))]
[else
;; idx is greater than index: nothing to do
(values node idx)]))
;; Just return the new tree (this is (nth-value 0 ...)).
(let-values ([(new-tree next-index)
(walk/indexed tree 0)])
new-tree))
Also jetzt
> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 4 '(- 4 2))
'(+ (* 5 6) (- 4 2))
> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 0 '(- 4 2))
'(- 4 2)
> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 20 '(- 4 2))
'(+ (* 5 6) (sqrt 3))
Es lohnt sich, oben ein passendes printfzu platzieren, walk/indexeddamit Sie sehen können, was es tut, wenn es über den Baum läuft.