Como faço para substituir parte de uma árvore por outra árvore no índice especificado?

Question

Suponha que eu tenha duas árvores:

• Árvore A - '(+ (* 5 6) (sqrt 3)):

  

• Árvore B - '(- 4 2):

  

Objetivo: substituir uma das subárvores da árvore A pela árvore B em uma posição de índice da árvore A especificada. A posição do índice começa em 0 no nó raiz e é a profundidade primeiro. Na figura da árvore A acima, rotulei todos os nós com seus índices para mostrar isso.

Por exemplo, (replace-subtree treeA 4 treeB)substitui a subárvore no índice 4 na árvore A pela árvore B, resultando na árvore (+ (* 5 6) (- 4 2)):

Como faço para implementar (replace-subtree treeA index treeB)?

---

Esta pergunta está um tanto relacionada à minha outra pergunta: Como faço para obter uma subárvore por índice? . Tive grande dificuldade em resolvê-lo, mas acabei encontrando uma solução viável para esse problema usando o estilo de passagem de continuação (CPS). No entanto, este problema aqui parece ser muito mais difícil. Estou completamente sem saber como devo começar! Implementações e dicas são bem-vindas. Eu estaria particularmente interessado em implementações que não usam call/cc.

---

EDITAR

Eu vim com uma implementação paliativa enquanto esperava por respostas. Depende set!, o que eu não prefiro.

(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))))

Answer 1

Este é um problema mais difícil do que eu esperava. Uma razão pela qual é difícil é que as coisas que você está chamando de 'árvores' não são realmente árvores: são DAGs (gráficos acíclicos direcionados) porque podem compartilhar subárvores. Simplesmente, isso só acontece para nós folha: nos (a b b)nós com índice 1 e 2 são eq?: eles são o mesmo objeto. Mas na verdade isso pode acontecer para qualquer nó: dado

(define not-a-tree
  (let ([subtree '(x y)])
    (list 'root subtree subtree)))

Os nós com índice 1 e 2 são o mesmo objeto e não são nós folha: este é um DAG, não uma árvore.

Isso é importante porque atrapalha uma abordagem óbvia:

1. encontre o nó com o índice no qual você está interessado;
2. caminhe sobre a árvore construindo uma nova árvore até encontrar este nó, usando eq?em nós, e então substitua-o.

Você pode ver que isso iria falhar se eu quisesse substituir o nó com índice 2 em (x y y): substituiria o nó com índice 1.

Uma abordagem que é, provavelmente, em seguida, o mais simples é tomar estas 'árvores' e transformá-los em árvores, onde nós não têm identidade. Em seguida, faça a substituição nessas árvores como acima e, em seguida, converta-as de volta à representação original. No entanto, isso possivelmente perderá alguma estrutura que importa: o objeto acima será transformado de um DAG em uma árvore, por exemplo. É improvável que isso importe na prática.

Então, para fazer isso, você precisaria de uma função para pegar as árvores antigas, transformá-las em novas árvores com exclusividade adequada e, em seguida, convertê-las de volta. Essa é quase certamente a abordagem conceitualmente mais simples, mas eu estava com preguiça de escrever todo aquele código.

Portanto, aqui está uma resposta que não é essa abordagem. Em vez disso, o que isso faz é percorrer a árvore acompanhando o índice do nó conforme ele avança e construindo uma nova árvore, se necessário. Para fazer isso, a coisa que entra em um nó precisa retornar duas coisas: um nó (que pode ser um nó recém-criado, ou seja, a substituição ou o nó original pelo qual foi passado) e o novo valor do índice. Isso é feito retornando dois valores do andador, e há uma boa quantidade de cabelo ao fazer isso.

Isso também não tenta usar algum pequeno subconjunto de Racket: ele usa vários valores, incluindo sintaxe ( let-values) que os torna menos dolorosos de usar e também for/foldpara fazer a maior parte do trabalho, incluindo dobrar vários valores. Então, você precisa entender essas coisas para ver o que ele faz. (Provavelmente também significa que não é adequado para uma resposta de dever de casa.)

Uma coisa que vale a pena notar é que o andador trapaceia um pouco: depois de fazer a substituição, ele nem tenta calcular o índice corretamente: apenas sabe que é maior do que se importa e sai correndo.

Primeiro, aqui estão as abstrações para lidar com árvores: observe que make-nodenão é exatamente o mesmo que make-nodena resposta à pergunta anterior: ele quer uma lista de filhos agora que é uma assinatura muito mais ú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
     '()]))

Agora, aqui está a função que faz o trabalho.

(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))

Então agora

> (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 a pena colocar um adequado printfno topo walk/indexedpara que você possa ver o que ele está fazendo enquanto caminha pela árvore.