¿Cómo reemplazo parte de un árbol con otro árbol en el índice especificado?
Supongamos que tengo dos árboles:
Árbol A -
'(+ (* 5 6) (sqrt 3)):
Árbol B -
'(- 4 2):
Objetivo: reemplazar uno de los subárboles del árbol A con el árbol B en una posición específica del índice del árbol A. La posición del índice comienza en 0 en el nodo raíz y es la profundidad primero. En la figura del árbol A anterior, he etiquetado todos los nodos con su índice para mostrar esto.
Por ejemplo, (replace-subtree treeA 4 treeB)reemplaza el subárbol en el índice 4 en el árbol A con el árbol B, lo que da como resultado el árbol (+ (* 5 6) (- 4 2)):
¿Cómo lo implemento (replace-subtree treeA index treeB)?
Esta pregunta está algo relacionada con mi otra pregunta: ¿Cómo obtengo un subárbol por índice? . Tuve una gran dificultad para resolverlo, pero finalmente encontré una solución viable para ese problema usando el estilo de continuación de paso (CPS). Sin embargo, este problema aquí parece ser mucho más difícil. ¡Estoy completamente perdido en cuanto a cómo debería comenzar! Las implementaciones y las pistas son bienvenidas. Estaría particularmente interesado en implementaciones que no usan call/cc.
EDITAR
Se me ocurrió una implementación provisional mientras esperaba respuestas. Se basa en set!lo que no prefiero.
(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))))
Respuestas
Este es un problema más difícil de lo que esperaba. Una razón por la que es difícil es que las cosas a las que llama "árboles" no son en realidad árboles: son DAG (gráficos acíclicos dirigidos) porque pueden compartir subárboles. Sencillamente, esto solo sucede para los nodos hoja: en (a b b)los nodos con índice 1 y 2 están eq?: son el mismo objeto. Pero, de hecho, puede suceder para cualquier nodo: dado
(define not-a-tree
(let ([subtree '(x y)])
(list 'root subtree subtree)))
Los nodos con índice 1 y 2 son el mismo objeto y no son nodos hoja: este es un DAG, no un árbol.
Esto es importante porque descarrila un enfoque obvio:
- busque el nodo con el índice que le interesa;
- camine sobre el árbol construyendo un nuevo árbol hasta que encuentre este nodo, usando
eq?en los nodos, y luego reemplácelo.
Puede ver que esto fallaría si quisiera reemplazar el nodo con el índice 2 en (x y y): reemplazaría el nodo con el índice 1 en su lugar.
Uno de los enfoques que probablemente es entonces la más simple es tomar estos 'árboles' y convertirlos en árboles donde los nodos no tienen identidad. Luego, haga el reemplazo en esos árboles como se indicó anteriormente, y luego conviértalos de nuevo a la representación original. Sin embargo, esto posiblemente perderá algo de estructura que importa: el objeto anterior se convertirá de un DAG a un árbol, por ejemplo. Es poco probable que eso importe en la práctica.
Entonces, para hacer esto, necesitaría una función para tomar los árboles viejos, convertirlos en árboles nuevos con la singularidad adecuada y luego convertirlos nuevamente. Este es casi con certeza el enfoque conceptualmente más simple, pero era demasiado vago para escribir todo ese código.
Entonces, aquí hay una respuesta que no es ese enfoque. En cambio, lo que hace es caminar sobre el árbol haciendo un seguimiento del índice de nodo a medida que avanza y construyendo un nuevo árbol si es necesario. Para hacer esto, lo que entra en un nodo necesita devolver dos cosas: un nodo (que puede ser un nodo recién creado, es decir, el nodo de reemplazo o el nodo original que se le pasó) y el nuevo valor del índice. Esto se hace devolviendo dos valores del caminante, y hay una buena cantidad de cabello alrededor haciendo eso.
Esto tampoco intenta usar un pequeño subconjunto de Racket: usa múltiples valores, incluida la sintaxis ( let-values) que los hace menos dolorosos de usar, y también for/foldpara hacer la mayor parte del trabajo, incluido el plegado de múltiples valores. Por lo tanto, deberá comprender esas cosas para ver qué hace. (También probablemente significa que no es adecuado para una respuesta de tarea).
Una cosa que vale la pena señalar es que el caminante hace un poco de trampa: una vez que se realiza el reemplazo, ni siquiera intenta calcular el índice correctamente: simplemente sabe que es más grande de lo que le importa y se retira.
Primero, aquí están las abstracciones para tratar con árboles: tenga en cuenta que make-nodeno es exactamente lo mismo que make-nodeen la respuesta a la pregunta anterior: ahora quiere una lista de niños, que es una firma mucho más útil.
(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
'()]))
Ahora aquí está la función que hace el trabajo.
(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))
Y ahora
> (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))
Vale la pena colocar un adecuado printfen la parte superior walk/indexedpara que pueda ver lo que hace mientras camina por el árbol.