Comment remplacer une partie d'un arbre par une autre à l'index spécifié?
Supposons que j'ai deux arbres:
Arbre A -
'(+ (* 5 6) (sqrt 3)):
Arbre B -
'(- 4 2):
Objectif: remplacer l'un des sous-arbres de l'arbre A par l'arbre B à une position d'index de l'arbre A spécifiée. La position d'index commence à 0 au nœud racine et est la profondeur d'abord. Dans la figure de l'arbre A ci-dessus, j'ai étiqueté tous les nœuds avec leur index pour le montrer.
Par exemple, (replace-subtree treeA 4 treeB)remplace le sous-arbre à l'index 4 dans l'arbre A par l'arbre B, ce qui donne l'arbre (+ (* 5 6) (- 4 2)):
Comment mettre en œuvre (replace-subtree treeA index treeB)?
Cette question est en quelque sorte liée à mon autre question: comment obtenir un sous-arbre par index? . J'ai eu beaucoup de mal à le résoudre, mais j'ai finalement trouvé une solution viable à ce problème en utilisant le style de passage continu (CPS). Cependant, ce problème semble ici beaucoup plus difficile. Je ne sais pas comment je devrais même commencer! Les mises en œuvre et les indices sont les bienvenus. Je serais particulièrement intéressé par les implémentations qui n'utilisent pas call/cc.
ÉDITER
J'ai proposé une mise en œuvre provisoire en attendant des réponses. Il s'appuie sur set!, ce que je ne préfère pas.
(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))))
Réponses
C'est un problème plus difficile que ce à quoi je m'attendais. L'une des raisons pour lesquelles c'est difficile est que les choses que vous appelez des «arbres» ne sont pas en fait des arbres: ce sont des DAG (graphes acycliques dirigés) parce qu'ils peuvent partager des sous-arbres. Simplement, cela ne se produit que pour les nœuds feuilles: dans (a b b)les nœuds d'index 1 et 2 se trouvent eq?: ils sont le même objet. Mais en fait cela peut arriver pour n'importe quel nœud: étant donné
(define not-a-tree
(let ([subtree '(x y)])
(list 'root subtree subtree)))
Les nœuds d'index 1 et 2 sont le même objet et ne sont pas des nœuds feuilles: c'est un DAG, pas un arbre.
Cela est important car cela fait dérailler une approche évidente:
- trouvez le nœud avec l'index qui vous intéresse;
- marchez sur l'arbre en construisant un nouvel arbre jusqu'à ce que vous trouviez ce nœud, en utilisant
eq?sur les nœuds, puis remplacez-le.
Vous pouvez voir que cela échouerait si je voulais remplacer le nœud par l'index 2 dans (x y y): cela remplacerait le nœud par l'index 1 à la place.
Une approche qui est sans doute alors le plus simple est de prendre ces « arbres » et les transformer en arbres où les nœuds n'ont l' identité. Effectuez ensuite le remplacement de ces arbres comme ci-dessus, puis reconvertissez-les dans la représentation d'origine. Cela risque cependant de perdre une certaine structure qui compte: l'objet ci-dessus sera par exemple transformé d'un DAG en arbre. Cela n'a pas d'importance dans la pratique.
Pour ce faire, vous aurez besoin d'une fonction pour prendre les vieux arbres, les transformer en nouveaux arbres avec un caractère unique approprié, puis les reconvertir. C'est presque certainement l'approche conceptuellement la plus simple, mais j'étais trop paresseux pour écrire tout ce code.
Alors, voici une réponse qui n'est pas cette approche. Au lieu de cela, cela permet de parcourir l'arborescence en gardant une trace de l'index des nœuds au fur et à mesure et en construisant un nouvel arbre si nécessaire. Pour ce faire, la chose qui entre dans un nœud doit renvoyer deux choses: un nœud (qui peut être un nœud nouvellement créé, c'est-à-dire le nœud de remplacement, ou le nœud d'origine auquel il a été passé), et la nouvelle valeur de l'index. Cela se fait en renvoyant deux valeurs du marcheur, et il y a une bonne quantité de cheveux autour de cela.
Cela n'essaie pas non plus d'utiliser un petit sous-ensemble de Racket: il utilise plusieurs valeurs, y compris la syntaxe ( let-values) qui les rend moins pénibles à utiliser, et aussi for/foldpour faire la plupart du travail, y compris le pliage de plusieurs valeurs. Donc, vous devrez comprendre ces choses pour voir ce que cela fait. (Cela signifie probablement aussi qu'il ne convient pas pour une réponse aux devoirs.)
Une chose à noter est que le marcheur triche un peu: une fois qu'il a terminé le remplacement, il n'essaye même pas de calculer correctement l'indice: il sait juste qu'il est plus gros que ce dont il se soucie et s'en sort.
Voici d'abord des abstractions pour traiter les arbres: notez que ce make-noden'est pas tout à fait la même chose que make-nodedans la réponse à la question précédente: il veut une liste d'enfants maintenant qui est une signature beaucoup plus utile.
(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
'()]))
Voici maintenant la fonction qui fait le travail.
(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))
Alors maintenant
> (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))
Cela vaut la peine de mettre un convenable printfau sommet walk/indexedpour que vous puissiez voir ce qu'il fait en marchant dans l'arbre.