지정된 인덱스에서 트리의 일부를 다른 트리로 어떻게 바꾸나요?

Nov 25 2020

두 개의 나무가 있다고 가정합니다.

  • 나무 A — '(+ (* 5 6) (sqrt 3)):

  • 나무 B — '(- 4 2):

목표 : 지정된 트리 A 인덱스 위치에서 트리 A의 하위 트리 중 하나를 트리 B로 교체합니다. 인덱스 위치는 루트 노드에서 0에서 시작하고 깊이 우선입니다. 위의 트리 A에 대한 그림에서이를 표시하기 위해 인덱스로 모든 노드에 레이블을 지정했습니다.

예를 들어, (replace-subtree treeA 4 treeB)트리 A의 인덱스 4에있는 하위 트리를 트리 B로 대체하면 트리가됩니다 (+ (* 5 6) (- 4 2)).

어떻게 구현 (replace-subtree treeA index treeB)합니까?


이 질문은 내 다른 질문과 다소 관련이 있습니다. 인덱스별로 하위 트리를 얻는 방법은 무엇입니까? . 해결하는 데 큰 어려움이 있었지만 결국 CPS (continuation-passing style)를 사용하여 해당 문제에 대한 실행 가능한 해결책을 찾았습니다. 그러나 여기서이 문제는 훨씬 더 어려운 것으로 보입니다. 나는 내가 어떻게 시작해야할지 완전히 잃어 버렸다! 구현과 단서는 환영합니다. .NET을 사용하지 않는 구현에 특히 관심이 있습니다 call/cc.


편집하다

답변을 기다리는 동안 임시 방편 구현을 생각해 냈습니다. set!내가 선호하지 않는 에 의존 합니다.

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

답변

2 tfb Nov 27 2020 at 12:03

이것은 내가 예상했던 것보다 더 어려운 문제입니다. 어려운 이유 중 하나는 '트리'라고 부르는 것이 실제로 트리가 아니기 때문입니다. 즉, 하위 트리를 공유 할 수 있기 때문에 DAG (방향성 비순환 그래프)입니다. 간단히 말해서 이것은 리프 노드에서만 발생합니다. (a b b)인덱스 1과 2가있는 노드 eq?에서는 동일한 객체입니다. 그러나 실제로 모든 노드에서 발생할 수 있습니다.

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

인덱스 1과 2가있는 노드는 동일한 개체이며 리프 노드가 아닙니다. 이것은 트리가 아니라 DAG입니다.

이것은 명백한 접근 방식을 탈선시키기 때문에 중요합니다.

  1. 관심있는 인덱스가있는 노드를 찾으십시오.
  2. 노드를 사용하여이 노드를 찾을 때까지 새 트리를 구성하는 트리를 걷다가 eq?교체하십시오.

노드를 인덱스 2로 바꾸고 싶을 때 실패한다는 것을 알 수 있습니다 (x y y). 대신 노드를 인덱스 1로 바꿉니다.

아마도 가장 간단한 접근 방식은 이러한 '트리'를 노드 가 ID 있는 트리로 바꾸는 것 입니다. 그런 다음 위와 같이 해당 트리를 교체 한 다음 다시 원래 표현으로 변환합니다. 그러나 이것은 중요한 구조를 잃을 수 있습니다. 예를 들어 위의 개체는 DAG에서 트리로 바뀝니다. 실제로는 중요하지 않습니다.

따라서 이렇게하려면 오래된 나무를 가져 와서 적절한 고유성을 가진 새 나무로 바꾼 다음 다시 변환하는 함수가 필요합니다. 이것은 거의 확실하게 개념적으로 가장 간단한 접근 방식이지만 모든 코드를 작성하기에는 너무 게으르다.

그래서 여기에 그 접근 방식 이 아닌 답변이 있습니다. 대신 이것이하는 일은 노드 인덱스를 추적하고 필요한 경우 새 트리를 구축하면서 트리를 걷는 것입니다. 이를 위해 노드로 들어가는 것은 두 가지를 반환해야합니다. 노드 (새로 만들어진 노드, 즉 교체 또는 전달 된 원래 노드 일 수 있음)와 인덱스의 새 값입니다. 이것은 워커로부터 두 개의 값을 반환함으로써 이루어지며, 주위에 상당한 양의 머리카락이 있습니다.

이것은 또한 Racket의 일부 하위 집합을 사용하려고 시도하지 않습니다. 구문 ( let-values)을 포함하여 여러 값 을 사용하여 사용하기가 덜 고통스럽고 for/fold여러 값 접기를 포함하여 대부분의 작업을 수행합니다. 그래서, 당신은 그것이 무엇을하는지보기 위해 그러한 것들을 이해해야 할 것입니다. (또한 숙제 답변에 적합하지 않음을 의미 할 수도 있습니다.)

주목할 가치가있는 한 가지는 워커가 약간의 속임수를 쓴다는 것입니다. 일단 교체가 완료되면 인덱스를 제대로 계산하려고 시도하지도 않습니다. 단지 그것이 신경 쓰는 것보다 더 크다는 것을 알고 경찰을 쫓아냅니다.

먼저 여기에 트리를 다루는 추상화 가 있습니다. 이전 질문에 대한 답변 make-node과 완전히 동일하지는 않습니다 make-node. 이제 훨씬 더 유용한 서명 인 자식 목록을 원합니다.

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

이제 작업을 수행하는 기능이 있습니다.

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

그래서 지금

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

나무 위를 걸 으면서 어떤 일을하는지 볼 수 있도록 적절한 printf것을 맨 위에 놓는 walk/indexed것이 좋습니다.