Восстановление деревьев по «отпечатку пальца» - PullRequest
Новая
       9

Восстановление деревьев по «отпечатку пальца»

0 голосов
/ 12 апреля 2010

Я провел исследование SO и Google и не нашел никого, кто занимался этим раньше, или, по крайней мере, никого, кто писал об этом.

Мой вопрос заключается в том, что, учитывая «универсальное» дерево произвольной высоты, в котором каждый узел может иметь произвольное количество ветвей, существует ли способ однозначно (и эффективно) «дактилоскопировать» произвольные поддеревья, начиная с « универсальный "корень дерева, такой, что, учитывая универсальное дерево и отпечаток дерева, я могу восстановить исходное дерево?

Например, у меня есть «универсальное» дерево (простите мои плохие иллюстрации), представляющее мою вселенную возможностей: 

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

и т.д.

У меня также есть дерево A, корневое поддерево моей вселенной 

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

Etc.

Есть ли способ «дактилоскопировать» дерево, чтобы с учетом этого отпечатка пальца и универсального дерева я мог восстановить А?

Я думаю о чем-то вроде хэша, сжатия или, возможно, функциональной / декларативной конструкции? Анализ Big-O (во времени или пространстве) является плюсом.

Например, вложенное выражение, подобное: {{(Root)},{(1),(2),(3)},{(2,3),(1),(4,5)}...}, представляющее фактические узлы, присутствующие на каждом уровне дерева, вероятно, допустимо, но может ли это быть сделано более эффективно?

1 Ответ

0 голосов
/ 12 апреля 2010

Я бы использовал список списков, где каждый элемент в списке указывает, сколько у вас детей:

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

Это дерево с двумя узлами на первом уровне, у левого дочернего узла есть один дочерний узел, а у правого дочернего узла 2 собственных.

Запустите этот вывод с помощью алгоритма сжатия без потерь по вашему выбору.

Вы также можете использовать обход дерева по глубине или любой другой тип обхода. Из того, что вам проще всего восстановить.

...