Слияние двух двоичных файлов

Question

Я хочу объединить две структуры дерева, но лучшая сложность, о которой я могу думать, это

Получить список значений из другого дерева: O(n), n - количество узлов в дереве. Вставьте все значения из списка вводной цели: n * O(m), m - длина ключа. Учитывая, что в худшем случае ключ имеет размер n, не сложность слияния O(n^2)?

Есть ли лучший способ сделать это?

Answer 1

Сложность будет O(N+M). Вам нужны два итератора (указатели на узлы дерева), оба запускаются на корневом узле соответствующих деревьев.

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

Таким образом, вы тратите время только на объединение неоднозначных узлов и можете копировать / перемещать целые поддеревья за один раз.

Если вы запустите исходную идею, сложность будет O(N*M), где N - количество записей, а m - средняя длина записи. Вы не получите O(N^2), потому что, если все узлы предназначены для одной записи (ваш худший случай), вам все равно нужно скопировать эту запись только один раз.