Два дерева K-Way эквивалентны, если связь между узлами поддерживается - PullRequest
Новая
       32

Два дерева K-Way эквивалентны, если связь между узлами поддерживается

0 голосов
/ 20 апреля 2020

Даны два k-way дерева, T1 и T2. Если любые два узла (A, B) из T1 имеют свойство, что узел B является потомком A, и эта связь поддерживается во втором дереве T2, то T1 эквивалентно T2. K-путь дерева определяется как дерево, в котором узел может иметь до k ветвей в узле. Определите, эквивалентны ли два k-way дерева.

Любые идеи относительно очень эффективного алгоритма с точки зрения как времени, так и пространства, и побейте его, будут оценены.

Например, T1 и T2 эквивалентны.

T1: 

        n1
      / |  \
     n2 n3  n4
    / \
   n5  n6
      / | \
     n7 n8 n9
             \
             n12

T2: 

        n10
      / |  \
     n3 n6  n2
    /   |    | \
   n15  n9   n0 n7

Моя попытка:

Составить список смежности T1: n1: {n2, n3, n4}, n2: {n5, n6}, n3: {}, n4: {}, n5: {}, n6: {n7, n8, n9}, n9: {n12 }, n12: {}

Составить список смежности T2: n10: {n3, n6, n2}, n6: {n9}, n2: {n0, n7}, ...

  1. Go для каждого узла в T2 и проверьте, находятся ли они в T1. Сохраните эти узлы.
  2. Создайте все возможные пары из этих узлов.
  3. Go для каждой пары, начните с одного узла в T1 и выполните команду dfs, чтобы увидеть, достигает ли он второго узла.

Например, ,

Pick (n9, n6). Используйте список смежности T1, чтобы увидеть, достижим ли n6 из n9. Это невозможно. В какой-то момент мы доберемся до пары (n6, n9) и начнем с n6. Доступен ли n9 из n6? Да.

Худшее пространство :

  • Предположим, num_nodes в T1 = num_x
  • Предположим, что num_nodes в T2 = num_y
  • В худшем случае пробел: O (num_x + num_y + (num_y * (num_y-1)) // // последний член для пар

Худшее время :

  • Время создания всех пар: O (num_y * (num_y-1))
  • Время, чтобы определить, достижимы ли два узла в T1, связанных в T1: O (высота T1) = O (h)
  • Общее время = O (h * num_y * (num_y-1))

Возможно, чтобы определить, достижимы ли два узла в T1, тур Эйлера и rmq может достичь его в O (1)

1 Ответ

0 голосов
/ 21 апреля 2020

Может быть эффективно решено с помощью обхода Эйлера по заданным деревьям.

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

Поместите узлы так, как они появляются в туре Эйлера, и для каждого узла хранятся два целых числа: начальный индекс в массиве тура Эйлера и конечный индекс в массиве. Конечный индекс - это индекс, в котором вы покидаете DFS этого узла при возврате его родителю. Обозначим эти массивы индексов st[] и en[]. Также сохраните его собственный индекс, чтобы мы могли позже запросить, какой индекс является самим узлом. Давайте назовем этот массив как idx[]

Теперь, выполняя DFS в T2 и избегая любых узлов, которые появляются в S, мы можем сформировать пары для отношения предка и потомка. Всего может быть O(m . m) таких пар в худшем случае для m = количество общих узлов в T2

Для любой пары A, D, чтобы проверить, является ли A предком D в T1 также используйте индексы, которые мы создали ранее для каждого узла T1 в своем туре Эйлера.

st[A] < idx[D] < en[A] тогда у нас есть эти отношения, иначе нет.

Общая сложность времени составляет O(m . m)

...