Найдите, является ли дерево поддеревом другого

Я предлагаю алгоритм, который использует предварительную обработку:

1) Предварительно обработайте дерево T1, сохраняя список всех возможных корней поддерева (список кеша будет содержать миллионы записей) ;

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

3) Используйте двоичный поиск, чтобы найти необходимое поддерево. Вы можете быстро отклонить поддеревья с количеством узлов, не равным числу узлов T2 (или с разной глубиной).

Обратите внимание, что шаги 1) и 2) должны выполняться только один раз, тогда вы можете протестировать многие кандидаты в поддерево, использующие тот же результат предварительной обработки.

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

Если вам известна глубина каждого отдельного узла 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 .

1,000,000 ) и дерево T2 будут иметь глубину 7 ( 2 ** 7 > 100 ). Вам просто нужно будет пройти 13 первых слоев из T1 (8192 узла - или это 14 слоев и 16384 узла?) И вы сможете пропустить около 90% T1 ...

Однако, если под поддеревом вы имеете в виду, что конечные узлы T2 также являются конечными узлами T1 , затем вы можете выполнить первый обход T1 и вычислить глубину каждого узла (расстояние от листа до узла), а затем проверить только поддеревья, которые имеют ту же глубину, что и T2 .

1,000,000 ) и дерево T2 будут иметь глубину 7 ( 2 ** 7 > 100 ). Вам просто нужно будет пройти 13 первых слоев из T1 (8192 узла - или это 14 слоев и 16384 узла?) И вы сможете пропустить около 90% T1 ...

Однако, если под поддеревом вы имеете в виду, что конечные узлы T2 также являются конечными узлами T1 , затем вы можете выполнить первый обход T1 и вычислить глубину каждого узла (расстояние от листа до узла), а затем проверить только поддеревья, которые имеют ту же глубину, что и T2 .

Я не уверен, верна ли моя идея. Тем не менее, для вашего увлечения.

1. Проведите обход по порядку в дереве 1 и дереве 2, назовите его P1 и P2.
2. Сравните P1 и P2. Если они разные. Дерево не поддерево. Выход.
3. Если они одинаковы, или P1 содержится в P2. Вы можете решить, какое из них является поддеревом.

Если вы ограничены памятью / хранилищем (т. Е. Не можете предварительно манипулировать и сохранять деревья в альтернативных формах), вы, вероятно, не сможете сделать что-либо лучше, чем поиск методом грубой силы предложены некоторыми другими ответами (пройти P1 в поисках совпадающего корня P2, пройти оба, чтобы определить, действительно ли узел является корнем совпадающего поддерева, продолжить исходный обход, если он не совпадает). Этот поиск выполняется за O (n * m), где n - размер P1, а m - размер P2. С проверками глубины и другими возможными оптимизациями в зависимости от имеющихся у вас данных дерева, этот человек может быть немного оптимизирован, но обычно он все равно O (n * m). В зависимости от ваших конкретных обстоятельств это может быть единственно разумным подходом.

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

Если дать корень обоих деревьев, и учитывая, что узлы одного типа, то почему недостаточно просто установить, что корень T2 находится в T1?

Я предполагаю, что "дано дерево T" означает дать указатель на корень T и тип данных узла.

Regards.

.