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

Question

Существует два двоичных дерева T1 и T2, в которых хранятся символьные данные, допускаются дубликаты.
Как я могу найти, является ли T2 поддеревом T1? .
T1 имеет миллионы узлов, а T2 имеет сотни узлов.

Answer 1

Траверс Т1. Если текущий узел равен корневому узлу T2, проходите оба дерева (T2 и текущее поддерево T1) одновременно. Сравните текущий узел. Если они всегда равны, T2 является поддеревом T1.

Answer 2

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

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

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

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

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

Answer 3

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

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

Привет.

Answer 4

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

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

Answer 5

Если ваши деревья никак не отсортированы, я не вижу другого способа, кроме как выполнить поиск brute-force : пройтись по дереву 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.

Answer 6

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

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

Answer 7

Один из простых способов - написать метод 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 << ')';
    }

И мы можем использовать некоторый оптимизированный алгоритм, например, Алгоритм Кнута-Морриса-Пратта , чтобы найти (возможно, за O (n) время) существование подстроки и, в конце концов, найти дерево это поддерево другого.

И снова строка может быть эффективно сжата с помощью Burrows – 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) (учитывая, что в отсортированных данных нет дубликатов).

Answer 8

Я предполагаю, что ваше дерево неизменных деревьев , поэтому вы никогда не меняете никакого поддерева (вы не делаете set-car! на языке Схемы), а просто строите новые деревья из листьев или из существующих деревьев .

Тогда я бы посоветовал сохранить в каждом узле (или поддерево) хеш-код этого узла. На языке C, объявите дерево s

 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 is

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, вы можете использовать методы, упомянутые в других ответах (или в руководствах).

Answer 9

Допустим, у нас есть 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, это поддерево.

Answer 10

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

Вам даны деревья T1 и T2, указатели, а не значения.

Если узел T2 (который является указателем), присутствует в дереве T1.

Тогда Дерево T2 является поддеревом T1.

---

Edit:

Только если сказано, что T2 на самом деле является другим деревом по объектам, и нам нужно выяснить, что если в T1 есть поддерево, которое идентично T2.

Тогда это не сработает.

И у нас нет другого выбора, кроме как перейти к решениям, которые уже обсуждались здесь.