Учитывая два двоичных дерева, вычислите их разность
3 ответа
Есть много способов сделать это.
Я бы посоветовал вам превратить дерево в отсортированный массив троек из (parent, child, direction). Итак, начните с дерева1:
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)
И теперь, если вы переместите поддеревья, они будут отображаться как большие различия. Но если вы просто измените один узел, это все равно будет небольшая разница.
Думайте о них как о директориях и печатайте отсортированный список пути к каждому элементу листа.
Дерево 1 становится:
4/2/10
4/2/22
4/3/5
4/3/8
Эти форматы списка могут быть diff [ 111], и дерево воссоздано из такого списка.
Есть много способов придумать работоспособную 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);