"지문"에서 나무 재구성

Question

나는 SO 및 Google 연구를 수행했으며,이 문제를 해결 한 사람 또는 적어도 이에 대해 작성한 사람을 찾지 못했습니다.

내 질문은 각 노드가 임의의 수의 브랜치를 가질 수있는 임의의 높이의 "보편적 인"트리가 주어진다는 것입니다. 임의의 하위 트리를 고유하게 (그리고 효율적으로) "지문 채취"하는 방법이 있습니다. 보편적 인 나무와 나무의 지문이 주어지면 원래 나무를 재구성 할 수있는 "보편적 인"나무의 뿌리?

 
       Root 
     ///| \ \ ... \ 
     O O O O O O  O (Level 1) 
     /|\/|\...................\ (Level 2) 

등

나는 또한이 나무 A, 뿌리 하위 트리의 :

는 예를 들어, 나는 가능성의 내 우주를 나타내는, (불쌍한 내 그림을 용서)는 "보편적 인"나무가 내 우주

 
     Root 
    //|\ \ 
    O O O O O 
    /

등

는 방법은 "F에 있는가 ingerprint "나무, 그 지문과 보편적 인 나무가 주어 지도록, 나는 A를 재구성 할 수 있었습니까?

해시, 압축 또는 기능/선언적 구성을 따라 뭔가를 생각하고 있습니까? Big-O 분석 (시간 또는 공간에서)은 장점입니다.

예를 들어, 트리의 각 레벨에있는 실제 노드를 나타내는 {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...}과 같은 중첩 된 표현식이 유효하지만 더 효율적으로 수행 할 수 있습니까?

Answer 1

나는이 목록의 각 요소는 당신이 얼마나 많은 아이들 상태 목록의 목록 사용한다 :

[[2][1,2][0,0,0]]

두 개의 첫 번째 수준의 노드와 왼쪽 아이가 하나를 가지고있는 나무입니다 자식 노드이고, 오른쪽 자식 노드는 자체 노드가 2 개 있습니다.

원하는 무손실 압축 알고리즘을 통해 출력을 실행하십시오.

트리의 깊이 우선 탐색이나 다른 모든 유형의 탐색을 실제로 사용할 수도 있습니다. 당신이 재구성 할 수있는 것이 가장 쉽습니다.