Есть 2 обычных сбалансированных (красно-черных) бинарных дерева. Получены путем добавления ключей в пустые деревья. Есть ли быстрый способ найти разницу между ними, т.е. ключи которые есть в одном и нет в другом.
Приходит в голову только тупой способ: перебирать ключи в одном дереве и искать в другом... Куда копать?   
Спасибо.

В красно-чёрных деревьях же значения упорядочены. Поэтому мы можем рассматривать эти два дерева просто как два отсортированных списка. Причём сам этот список в явном виде можно получить по дереву за линейное относительно числа вершин время (просто обходом по дереву).

А найти разницу между двумя отсортированными списками очень легко, опять же за линейное время. Это известный метод двух движущихся указателей: сначала оба указателя указывают на начала списков (первый-на первый список, второй-на второй). Потом, пока по одному указателю число меньше, чем по другому - этот указатель двигаем на 1 вправо, ответ увеличиваем на 1. Когда окажется, что по обоим указателям стоят одинаковые числа, оба указателя продвигаем вправо (как минимум на 1, ну или, если элементы в списках могут повторяться, то пока не встретим первый отличный от старого элемент). Ну и в самом конце могло оказаться, что один из указателей уже указывает за конец списка, а другой ещё нет - тогда в ответ добавляются все оставшиеся числа (от второго указателя и дальше).

Делаешь обход в ширину обоих деревьев  результат заносим в массивы, а после сравниваем массивы за один проход.

В идеале совместить в один проход для этого рекурсию заменить циклом. 

Можно посмотреть разницу в объеме занимаемой памяти.  
Можно посчитать Контрольную сумму для каждого, или делать ето на моменте заполнения, а потом сравнить.
Способов много есть, скажи для чего нада, мож что то конкретнее придумаем? 

Это сообщение отредактировал(а) niteo - 23.9.2009, 15:41

Всем спасибо!


maxdiver, просто как дважды два. То что надо! Держи +1.