Учитывая два двоичных дерева, вычислите их разность

Question

Мой друг задал этот вопрос в интервью.

Учитывая два двоичных дерева, объясните, как бы вы создали разность, такую, что , если у вас есть этот разност, и любое из деревьев вы сможете сгенерировать другое двоичное дерево . Реализуйте функцию createDiff(Node tree1, Node tree 2), возвращающую эту разницу.

Tree 1
       4
     /   \
    3     2
   / \   /  \
  5   8 10   22

Tree 2
       1
         \
          4
         /  \
       11   12

Если вам дано Дерево 2 и разница, вы сможете сгенерировать Дерево 1.

Мое решение: Преобразуйте оба бинарных дерева в массив, где левый потомок находится в 2n+1, а правый потомок - в 2n+2 и представляет пустой узел -1. Затем просто выполните поэлементное вычитание массива, чтобы создать разность. Это решение потерпит неудачу, если дерево имеет значение -1 в качестве значения узла, и я думаю, что должно быть лучшее и аккуратное решение, но я не могу понять это.

Answer 1

Есть много способов придумать работоспособную diff-структуру.

Наивный раствор

Один наивный способ - хранить два дерева в кортеже. Затем, когда вам нужно восстановить дерево с учетом другого и различий, вы просто ищете узел, который отличается при сравнении данного дерева с деревом в первой записи кортежа различий. Если найдено, вы возвращаете это дерево из первой записи кортежа. Если не найдено, вы возвращаете второй из кортежа различий.

Маленькие различия для небольших различий

Интервьюер, вероятно, попросил бы альтернативу с меньшим объемом памяти Можно попытаться придумать структуру, которая будет небольшой по размеру, когда есть только несколько значений или узлов. В крайнем случае, когда оба дерева равны, такой diff будет (почти) пустым.

Определения

Я определяю эти термины перед тем, как определить структуру diff:

• Представьте, что деревья получают дополнительные листовые узлы NIL, то есть пустое дерево будет состоять из 1 узла NIL. Дерево, имеющее только корневой узел, будет иметь два узла NIL в качестве своих прямых потомков и т. Д.

• Узел является общим для обоих деревьев, когда к нему можно добраться по одному и тому же пути от корня (например, слева направо), независимо от того, содержат ли они одинаковое значение или имеют одинаковые дочерние элементы. Узел может даже быть общим, когда он является узлом NIL в одном или обоих деревьях (как определено выше).

• Общие узлы (включая узлы NIL, когда они общие) получают порядковый номер предзаказа (0, 1, 2, ...). Узлы, которые не общие, отбрасываются при этой нумерации.

Различная структура

Разница может быть в списке кортежей, где каждый кортеж имеет эту информацию:

• Вышеупомянутый порядковый номер предзаказа, идентифицирующий общий узел
• Значение: когда ни один из узлов не является узлом NIL, это разница значений (например, XOR). Когда один из узлов является узлом NIL, значением является объект другого узла (так эффективно, включая целое поддерево под ним). В типизированных языках любая информация может помещаться в одну и ту же позицию кортежа. В строго типизированных языках вы должны использовать дополнительную запись в кортеже (например, atomicValue, поддерево), где только один из двух будет иметь значительное значение.

Кортеж будет добавлен только для общего узла и только тогда, когда любое из их значений будет отличаться, и хотя бы один из них будет не-NIL-узлом.

Алгоритм

Различия могут быть созданы путем предварительного заказа через общие узлы деревьев.

Вот реализация на JavaScript:

class Node {
    constructor(value, left, right) {
        this.value = value;
        if (left) this.left = left;
        if (right) this.right = right;
    }
    clone() {
        return new Node(this.value, this.left ? this.left.clone() : undefined,
                                    this.right ? this.right.clone() : undefined); 
    }
}

// Main functions:
function createDiff(tree1, tree2) {
    let i = -1; // preorder sequence number
    function recur(node1, node2) {
        i++;
        if (!node1 !== !node2) return [[i, (node1 || node2).clone()]];
        if (!node1) return [];
        const result = [];
        if (node1.value !== node2.value) result.push([i, node1.value ^ node2.value]);
        return result.concat(recur(node1.left, node2.left), recur(node1.right, node2.right));
    }
    return recur(tree1, tree2);
}

function applyDiff(tree, diff) {
    let i = -1; // preorder sequence number
    let j = 0; // index in diff array
    function recur(node) {
        i++;
        let diffData = j >= diff.length || diff[j][0] !== i ? 0 : diff[j++][1];
        if (diffData instanceof Node) return node ? undefined : diffData.clone();
        return node && new Node(node.value ^ diffData, recur(node.left), recur(node.right));
    }
    return recur(tree);
}

// Create sample data:
let tree1 = 
    new Node(4,
        new Node(3,
            new Node(5), new Node(8)
        ),
        new Node(2,
            new Node(10), new Node(22)
        )
    );
let tree2 =
    new Node(2,
        undefined,
        new Node(4,
            new Node(11), new Node(12)
        )
    );

// Demo:
let diff = createDiff(tree1, tree2);
console.log("Diff:");
console.log(diff);

const restoreTree2 = applyDiff(tree1, diff);
console.log("Is restored second tree equal to original?");
console.log(JSON.stringify(tree2)===JSON.stringify(restoreTree2));

const restoreTree1 = applyDiff(tree2, diff);
console.log("Is restored first tree equal to original?");
console.log(JSON.stringify(tree1)===JSON.stringify(restoreTree1));

const noDiff = createDiff(tree1, tree1);
console.log("Diff for two equal trees:");
console.log(noDiff);

Answer 2

Есть много способов сделать это.

Я бы посоветовал вам превратить дерево в отсортированный массив троек (parent, child, direction). Итак, начнем с tree1:

       4
     /   \
    3     2
   / \   /  \
  5   8 10   22

Это быстро становится:

(None, 4, None) # top
(4, 3, L)
(3, 5, L)
(3, 8, L)
(4, 2, R)
(2, 10, L)
(2, 22, R)

Что вы сортируете, чтобы получить

(None, 4, None) # top
(2, 10, L)
(2, 22, R)
(3, 5, L)
(3, 8, L)
(4, 2, R)
(4, 3, L)

Сделайте то же самое с другими, а затем сравните их.

Учитывая дерево и разницу, вы можете сначала превратить дерево в эту форму, посмотреть на разницу, понять, в каком направлении это происходит, и получить желаемое представление с помощью патча. Затем вы можете рекурсивно восстановить другое дерево.

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

---

Редактировать

Для точки из @ruakh предполагается, что значения не повторяются в дереве. Если они это сделают, то вы можете сделать такое представление:

       4
     /   \
    3     2
   / \   /  \
  5   8 10   22

становится

(, 4)
(0, 3)
(00, 5)
(01, 8)
(1, 2)
(10, 10)
(11, 22)

А теперь, если вы переместите поддеревья, они будут отображаться как большие различия. Но если вы просто измените один узел, это все равно будет небольшая разница.

Answer 3

(Пример из вопроса (/ интервью) не очень полезен для того, чтобы не показывать какую-либо общую подструктуру нетривиального размера. Или не задан вопрос об интервью для инициирования диалога между заказчиком и разработчиком.)
Re-использование поддеревьев нуждается в представлении, позволяющем идентифицировать его.Кажется полезным иметь возможность восстановить меньшее дерево, не проходя большую часть разницы.Обозначение «определения» идентифицируемых поддеревьев заглавными буквами и повторного использования с помощью прикрепленного символа:

     d            e             d--------e
  c     b "-"   c    b   =>   C   B'   C'  b
 b a   a       b a    a      B a            a
a             a             a

(Оператор задачи не скажем, diff является линейным .)
Что следует отметить:

• есть поддерево B , встречающееся в двух местах T1
• в T2 есть еще один b с одним листом-потомком a , то есть не другой случай B
• нет попыток поделиться листьями

Что, если теперь я представляю (или интервьюер предлагает) два огромных дерева, идентичных, но для одного узла где-то в середине, который имеет другое значение ?
Ну, по крайней мере, его поддеревья будут общими, а "остальные поддеревья" - вплоть до корня.Очень плохо, если деревья вырождены и почти все узлы являются частью этого пути.
Заменены огромные деревья с потомками корня?
(Обнаружение деревьев, встречающихся более одного раза, имеет шанс на сияниездесь.)
Большей проблемой могло бы казаться, что целые деревья представлены в "diff", в то время как требование может быть

. Для одного дерева diff должноподдержка реконструкции другого, используя мало места и обработки.

(Это может включать , настройка diff тоже должна быть дешевой - что я бы сразу бросил вызов: small diff выглядит как расстояние редактирования .)
Способ определить"критические узлы" в каждом дереве необходимо - предложение btilly "left"-права-строка " хороша как золото.
Тогда нужен способ сохранить различия в детях и ценности.

---

Это дальний конец, на котором я ожидал бы обменв интервью, чтобы достичь.

Чтобы обнаружить повторно используемые деревья, я бы добавил height к каждому внутреннему узлу .Для доказательства принципа я бы, вероятно, использовал существующую реализацию для поиска повторяющихся строк в подходящей сериализации.

Answer 4

Думайте о них как о директориях и печатайте отсортированный список путей к каждому элементу листа

Дерево 1 становится:

4/2/10
4/2/22
4/3/5
4/3/8

Эти форматы списка могут быть diff 'ed и дерево воссоздано из такого списка.