Далее предполагается, что наборы хранятся в виде отсортированного контейнера (как это делает std :: set).
Существует общий алгоритм объединения двух упорядоченных списков для получения третьего. Идея состоит в том, что когда вы смотрите на заголовки двух списков, вы можете определить, какой из них ниже, извлечь его и добавить в конец вывода, а затем повторить.
Существуют варианты, которые обнаруживают случай, когда две головы равны, и обрабатывают это специально. Примеры пересечений и объединений - примеры этого.
При заданной асимметричной разнице ключевым моментом является то, что для A-B, когда вы извлекаете головку B, вы отбрасываете ее. Когда вы извлекаете головку A, вы добавляете ее ко входу , если голова B не равна, и в этом случае вы тоже извлекаете это и отбрасываете оба.
Хотя этот подход разработан для структур данных с последовательным доступом (и хранилищ на магнитной ленте и т. Д.), Иногда бывает очень полезно сделать то же самое для структуры данных с произвольным доступом, если в любом случае достаточно эффективен последовательный доступ к ней. И вам не обязательно извлекать что-то по-настоящему - вместо этого вы можете скопировать и выполнить шаг.
Ключевым моментом является то, что вы последовательно просматриваете входы, всегда следя за наименьшим оставшимся значением, следующим за ним, чтобы (если на входах не было дубликатов) вы выполняли сопоставляемые элементы. Поэтому вы всегда знаете, является ли ваше следующее наименьшее значение для обработки элементом из A, в котором нет совпадений в B, и элементом в B, в котором нет совпадений в A, или элементом, равным как в A, так и в B.
В более общем смысле алгоритм для разности множеств зависит от представления множества. Например, если набор представлен в виде битового вектора, вышеупомянутое будет слишком сложным и медленным - вы просто зациклились бы на векторах, выполняя побитовые операции. Если набор представлен в виде хеш-таблицы (как в tr1 unordered_set), это неверно, так как требует упорядоченных входных данных.
Если у вас есть собственный двоичный код дерева, который вы используете для наборов, один хороший вариант - преобразовать оба дерева в связанные списки, поработать со списками, а затем преобразовать полученный список в идеально сбалансированное дерево. Разница в наборе связанных списков очень проста, и эти два преобразования можно повторно использовать для других аналогичных операций.
EDIT
По сложности - использование этих упорядоченных алгоритмов, подобных слиянию, является O (n) при условии, что вы можете выполнять обходы в порядке упорядочения в O (n). Преобразование в список и обратно также является O (n), поскольку каждый из трех шагов - это O (n) - дерево-список, набор-разность и список-дерево.
Tree-to-list в основном выполняет обход в глубину, деконструируя дерево по мере его прохождения. Есть хитрость в том, чтобы сделать это итеративным, сохранив «стек» в узлах с частичной обработкой - изменив указатель левого потомка на указатель родителя непосредственно перед тем, как перейти к левому потомку. Это хорошая идея, если дерево может быть большим и несбалансированным.
Преобразование списка в дерево в основном включает в себя обход в глубину воображаемого дерева (на основе размера, известного с самого начала), строящего его по-настоящему на ходу. Например, если дерево имеет 5 узлов, вы можете сказать, что корнем будет узел 3. Вы рекурсивно строите левое поддерево с двумя узлами, затем берете следующий элемент из списка для этого корня, а затем рекурсивно строите два. правое поддерево.
Преобразование списка в дерево не нужно реализовывать итеративно - рекурсивно хорошо, так как результат всегда идеально сбалансирован. Если вы не можете обработать глубину рекурсии log n, вы почти наверняка не сможете обработать полное дерево.