Блог

Я ищу алгоритм, который находит минимальные изменения (вставка, удаление, перемещение), чтобы перейти от tree1 к tree2 .

Дерево является общим и уникально помеченным деревом. Это означает, что значение каждого узла является своего рода уникальным идентификатором, например, UUID. У каждого узла могут быть дочерние узлы, и порядок этих дочерних узлов важен. Пример дерева 1

 A
 - B
 - C
   - D
   - E
 - F
 

Пример дерева 2

 A
 - B
 - F
  - C
    - D
 - G
 

ожидаемые изменения от дерева 1 к дереву 2

 move(atIndex: 1, inParent: A, toIndex: 0, inParent: F)
delete(atIndex: 1, inParent: C)
insert(atIndex: 2, inParent: A)
 

Мне это нужно для приложения macOS для анимации изменений в NSOutlineView.
Я нашел несколько алгоритмов для поиска изменений между общими деревьями, но только для упорядоченных и помеченных деревьев и ни одного для деревьев с уникальными метками.
Алгоритмы для семы деревьев с неуникальными метками действительно сложны, и я подумал, что если метки уникальны, должен быть более простой и эффективный алгоритм.

Кстати: NSOultineView не имеет корневого узла, а представляет собой массив узлов в начале. Я не знаю, важно ли это.

Вы правы — уникальность метки упрощает проблему.

Для каждой метки, присутствующей в обоих деревьях, вычислите последовательность операций для редактирования ее дочерних элементов. Это включает в себя вычисление самой длинной общей подпоследовательности и выдачу соответствующих перемещений / вставок / удалений для всех узлов, не входящих в эту подпоследовательность. (В случае, если метка присутствует в обоих деревьях, но с разными родителями, мы должны подавить удаление для старого родителя.)

Этот набор операций представляет собой нижнюю границу, но если мы просто выполним их, мы можем столкнуться с ситуацией, когда мы пытаемся переместить узел под одним из его потомков. Возможно, достаточно определить, когда это должно произойти, и разделить его на два хода. Если вам действительно нужна оптимальная последовательность ходов, то я думаю, что необходимо решить проблему с набором дуг / узлов обратной связи, хотя здесь это может быть не сложно из-за древовидной структуры.

Учитывая, что метки уникальны, я не уверен, что «минимальные» изменения чем-то отличаются от определения различий для полного пути каждого узла.

Если мы посмотрим на путь справа налево, мы увидим, что первый родительский элемент и индекс D ниже не изменились.

Похоже, что минимальные изменения, представленные в описании вопроса, предполагают, что перемещение F с индекса 2 на 1 происходит волшебным образом, когда C перемещается на 1. Но скорее два действия «переместить C» и «переместить F на прежнее место C», которые мы получили бы, просто изучив пути, включают в себя фактическое поведение, которое должно было бы произойти из-за предположения в вашем текущем «перемещении C.»

 Example tree 1
A        ⊥
 - B     A 0
 - C     A 1
   - D   A C 0
   - E   A C 1
 - F     A 2
 
Example tree 2
A          ⊥
 - B       A 0
 - F      *A 1
   - C    *A 1 F 0
     - D  *A 1 F 0 C 0
 - G       A 2