Определите, является ли дерево поддеревом других
https://stackoverflow.com/questions/1017821
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Существует два двоичных дерева T1 и T2, в которых хранятся символьные данные, допускаются дубликаты.
Как я могу определить, является ли T2 поддеревом T1 ?.
T1 имеет миллионы узлов, а T2 - сотни узлов.
Решение
Траверс Т1. Если текущий узел равен корневому узлу T2, проходите оба дерева (T2 и текущее поддерево T1) одновременно. Сравните текущий узел. Если они всегда равны, T2 является поддеревом T1.
Другие советы
Я предлагаю алгоритм, который использует предварительную обработку:
1) Предварительная обработка дерева T1 с сохранением списка всех возможных корней поддеревьев (список кэша будет содержать миллионы записей);
2) Сортировать кэшированный список корней по убыванию данных, сохраненных в корне. Вы можете выбрать более элегантную функцию сортировки, например, проанализировать дерево символов в строку.
3) Используйте бинарный поиск, чтобы найти нужное поддерево. Вы можете быстро отклонить поддеревья с количеством узлов, не равным количеству узлов T2 (или с разной глубиной).
Обратите внимание, что шаги 1) и 2) должны быть выполнены только один раз, тогда вы можете протестировать множество кандидатов на поддеревья, используя один и тот же предварительно обработанный результат.
Если ваши деревья никак не отсортированы, я не вижу другого пути, кроме как выполнить поиск brute-force : пройтись по дереву Если вы знаете глубину каждого узла Однако, если под поддеревом вы подразумеваете, что конечные узлы T1 и проверить чтобы увидеть, достигнете ли вы узла, который соответствует первому узлу дерева T2 . Если нет, продолжайте обходить T1 . Если это так, проверьте, совпадают ли следующие узлы, пока не найдете конец T2 , и в этом случае у вас есть попадание: ваше дерево T2 действительно является поддеревом Т1 .
T1 (от листа к узлу), вы можете пропустить любые узлы, которые не настолько глубоки, как искомое поддерево. Это может помочь вам избежать множества ненужных сравнений. Скажем, что T1 и T2 хорошо сбалансированы, тогда дерево T1 будет иметь общую глубину 20 ( 2 ** 20 > 1 000 000 ) и дерево T2 будут иметь глубину 7 ( 2 ** 7 > 100 ). Вам просто нужно пройти 13 первых слоев из T1 (8192 узла - или это 14 слоев и 16384 узла?), И вы сможете пропустить около 90 % от T1 ... T2 также являются конечными узлами T1 , то вы можете выполнить первый обход из T1 и вычислите глубину каждого узла (расстояние от листа до узла), а затем проверьте только те поддеревья, которые имеют ту же глубину, что и T2 .
Если вы ограничены памятью / хранилищем (т.е. не можете предварительно манипулировать и хранить деревья в альтернативных формах), вы, вероятно, не сможете сделать ничего лучше, чем поиск методом грубой силы, предложенный некоторыми другими ответами (traverse). P1 ищет соответствующий корень P2, пройдитесь по обоим, чтобы определить, является ли узел на самом деле корнем соответствующего поддерева, продолжайте исходный обход, если он не совпадает). Этот поиск работает в O (n * m), где n - размер P1, а m - размер P2. С проверками глубины и другими потенциальными оптимизациями, зависящими от имеющихся у вас данных дерева, этот человек будет немного оптимизирован, но обычно он все равно O (n * m). В зависимости от ваших конкретных обстоятельств, это может быть единственным разумным подходом.
Если вы не ограничены памятью / хранилищем и не возражаете против небольшой сложности, я считаю, что это можно улучшить до O (n + m), сократив до проблема самой длинной общей подстроки с помощью обобщенное суффиксное дерево . Некоторое обсуждение этой проблемы можно найти в здесь . Может быть, когда у меня будет больше времени, я вернусь и отредактирую детали с реализацией.
Если задан корень обоих деревьев и учитывая, что узлы имеют один и тот же тип, почему тогда просто констатировать, что корень T2 находится в T1, недостаточно?
Я предполагаю, что "задано дерево T" означает, что задан указатель на корень T и тип данных узла.
С уважением.
Я не уверен, верна ли моя идея. Тем не менее, для вашего личного. <Ол>
Я думаю, нам нужно использовать грубую силу, но зачем вам сопоставлять деревья после того, как вы нашли свой корень из T2 в T1?Это не то же самое, что когда мы не должны находить, идентичны ли деревья.(Тогда только нам нужно сравнить все дерево)
Вам даны деревья T1 и T2, указатели, а не значения.
Если узел T2 (который является указателем) присутствует в дереве T1.
Тогда дерево T2 является поддеревом T1.
Редактировать:
Только если сказано, что T2 на самом деле является другим деревом по объекту, и нам нужно выяснить, есть ли поддерево в T1, которое идентично T2.
Тогда это не сработает.
И у нас нет другого выбора, кроме как прибегнуть к решениям, уже обсуждавшимся здесь.
Допустим, у нас есть T1 как родительское дерево и T2 как дерево, которое может быть поддеревом T1. Сделайте следующее. Предполагается, что T1 и T2 являются двоичным деревом без какого-либо уравновешивающего фактора.
1) Поиск корня T2 в T1. Если не найден, T2 не является поддеревом. Поиск элемента в BT займет O (n) времени.
2) Если элемент найден, выполняется предварительный обход T1 от корневого элемента узла T2. Это займет o (n) время. Сделайте также предварительный заказ T2. Займет O (N) время. Результат прохождения предварительного заказа может быть сохранен в стек. Вставка в стек займет только O (1).
3) Если размер двух стеков не равен, T2 не является поддеревом.
4) Извлечь по одному элементу из каждого стека и проверить на равенство. Если происходит несоответствие, T2 не является поддеревом.
5) Если все элементы соответствуют T2, это поддерево.
Я предполагаю, что ваше дерево - это неизменяемые деревья таким образом, вы никогда не меняете ни одно поддерево (вы этого не делаете set-car! на языке схемы), но просто вы строите новые деревья из листьев или из существующих деревьев.
Тогда я бы посоветовал храните в каждом узле (или поддерево) хэш- код этого узла.На языке Си объявите дерево-ы как
struct tree_st {
const unsigned hash;
const bool isleaf;
union {
const char*leafstring; // when isleaf is true
struct { // when isleaf is false
const struct tree_st* left;
const struct tree_st* right;
};
};
};
затем вычислите хэш во время построения, и при сравнении узлов на равенство сначала сравните их хэш на равенство;в большинстве случаев хэш-код будет отличаться (и вы не будете утруждать себя сравнением содержимого).
Вот возможная функция построения листа:
struct tree_st* make_leaf (const char*string) {
assert (string != NULL);
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
t->hash = hash_of_string(string);
t->isleaf = true;
t->leafstring = string;
return t;
}
Функцией для вычисления хэш-кода является
unsigned tree_hash(const struct tree_st *t) {
return (t==NULL)?0:t->hash;
}
Функция для построения узла из двух поддеревьев sleft & sright является
struct tree_st*make_node (const struct tree_st* sleft,
const struct tree_st* sright) {
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
/// some hashing composition, e.g.
unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
t->hash = h;
t->left = sleft;
t->right = sright;
return t;
}
Функция сравнения (двух деревьев tx & ty) воспользуйтесь преимуществом, что если хэш-коды разные, то и сравнительные значения разные
bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
if (tx==ty) return true;
if (tree_hash(tx) != tree_hash(ty)) return false;
if (!tx || !ty) return false;
if (tx->isleaf != ty->isleaf) return false;
if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
else return equal_tree(tx->left, ty->left)
&& equal_tree(tx->right, ty->right);
}
Большую часть времени tree_hash(tx) != tree_hash(ty) тест пройдет успешно, и вам не придется повторять процедуру.
Читайте о приготовление хэша.
Как только у вас появится такой эффективный хэш-файл, основанный equal_tree функция вы могли бы использовать методы, упомянутые в других ответах (или в справочниках).
Один из простых способов - написать метод is_equal () для дерева и выполнить следующие действия:
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
Обратите внимание, что is_equal () можно оптимизировать, используя хеш-код для дерева. Это можно сделать простым способом, взяв высоту дерева или количество дочерних элементов или диапазон значений в качестве хэш-кода.
bool is_equal(TNode*other) {
if(x != other->x) return false;
if(height != other->height) return false;
if(nchildren != other->nchildren) return false;
if(hashcode() != other->hashcode()) return false;
// do other checking for example check if the children are equal ..
}
Когда дерево похоже на связанный список, это займет O (n) времени. Мы также можем использовать эвристику при выборе детей для сравнения.
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
if(is_equal(other)) return true;
if(left == NULL || right == NULL) {
return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
if(left->nchildren < right->nchildren) { // find in smaller child tree first
return (left->contains_subtree(other)) || right->contains_subtree(other);
} else {
return (right->contains_subtree(other)) || left->contains_subtree(other);
}
}
Другой способ - сериализовать оба дерева в виде строки и определить, является ли вторая строка (сериализованная из T2) подстрокой первой строки (сериализованной из T1).
Следующий код сериализуется в предзаказе.
void serialize(ostream&strm) {
strm << x << '(';
if(left)
left->serialize(strm);
strm << ',';
if(right)
right->serialize(strm);
strm << ')';
}
И мы можем использовать некоторый оптимизированный алгоритм, например, Кнут & # 8211; Morris & # 8211; Алгоритм Пратта , чтобы найти (возможно, за O (n) время) существование подстроки и, в конечном итоге, найти, является ли дерево поддеревом другого.
И снова строку можно эффективно сжать с помощью Burrows & # 8211; Wheeler_transform. И можно bzgrep искать подстроку в сжатых данных.
Другой способ - отсортировать поддеревья в дереве по высоте и количеству дочерних элементов.
bool compare(TNode*other) {
if(height != other->height)
return height < other->height;
return nchildren < other->nchildren;
}
Обратите внимание, что будет O (n ^ 2) поддеревьев. Чтобы уменьшить число, мы можем использовать некоторый диапазон, основанный на высоте. Например, нас могут интересовать только поддеревья высотой от 1000 до 1500.
Когда генерируются отсортированные данные, можно выполнить в них двоичный поиск и определить, является ли оно подмножеством за O (lg n) времени (учитывая, что в отсортированных данных нет дубликатов).
