Как найти наибольшее общее поддерево в данных двух бинарных деревьях поиска?

Question

Два BSTs (деревья бинарного поиска). Как найти наибольшее общее поддерево в данных двух binary trees?

РЕДАКТИРОВАТЬ 1: Вот что я подумал:

Пусть, r1 = текущий узел 1-го дерева r2 = текущий узел 2-го дерева

There are some of the cases I think we need to consider:

Case 1 : r1.data < r2.data
     2 subproblems to solve:
     first, check r1 and r2.left 
     second, check r1.right and r2

Case 2 : r1.data > r2.data
     2 subproblems to solve:
       - first, check r1.left and r2
       - second, check r1 and r2.right

Case 3 : r1.data == r2.data
     Again, 2 cases to consider here:
     (a) current node is part of largest common BST
         compute common subtree size rooted at r1 and r2
     (b)current node is NOT part of largest common BST
         2 subproblems to solve:
         first, solve r1.left and r2.left 
         second, solve r1.right and r2.right

Я могу вспомнить случаи, которые нам нужно проверить, но я не могу сейчас их кодировать. И это НЕ домашняя проблема. Как это выглядит?

Answer 1

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

ret = -1
// T is a tree node, H is a hash set, and first is a boolean flag
hashTree(T, H, first):
  if (T is null):
    return 0 // leaf case
  h = hash(hashTree(T.left, H, first), hashTree(T.right, H, first), T.key)
  if (first):
    // store hashes of T1's nodes in the set H
    H.insert(h)
  else:
    // check for hashes of T2's nodes in the set H containing T1's nodes
    if H.contains(h):
      ret = max(ret, size(T)) // size is recursive and memoized to get O(n) total time
  return h

H = {}
hashTree(T1, H, true)
hashTree(T2, H, false)
return ret

Обратите внимание, что это предполагает стандартное определение поддерева BST, а именночто поддерево состоит из узла и всех его потомков.

Answer 2

Если в деревьях нет повторяющихся значений:

LargestSubtree(Tree tree1, Tree tree2)
    Int bestMatch := 0
    Int bestMatchCount := 0
    For each Node n in tree1  //should iterate breadth-first
        //possible optimization:  we can skip every node that is part of each subtree we find
        Node n2 := BinarySearch(tree2(n.value))
        Int matchCount := CountMatches(n, n2)
        If (matchCount > bestMatchCount)
            bestMatch := n.value
            bestMatchCount := matchCount
        End
    End

    Return ExtractSubtree(BinarySearch(tree1(bestMatch)), BinarySearch(tree2(bestMatch)))
End

CountMatches(Node n1, Node n2)
    If (!n1 || !n2 || n1.value != n2.value)
        Return 0
    End
    Return 1 + CountMatches(n1.left, n2.left) + CountMatches(n1.right, n2.right)
End

ExtractSubtree(Node n1, Node n2)
    If (!n1 || !n2 || n1.value != n2.value)
        Return nil
    End

    Node result := New Node(n1.value)
    result.left := ExtractSubtree(n1.left, n2.left)
    result.right := ExtractSubtree(n1.right, n2.right)
    Return result
End

Вкратце, это грубое решение проблемы. Он делает первую прогулку в ширину первого дерева. Для каждого узла он выполняет BinarySearch второго дерева, чтобы найти соответствующий узел в этом дереве. Затем, используя эти узлы, он оценивает общий размер общего поддерева, укорененного там. Если поддерево больше, чем любое ранее найденное поддерево, оно запоминает его для дальнейшего использования, чтобы оно могло создать и вернуть копию наибольшего поддерева после завершения алгоритма.

Этот алгоритм не обрабатывает повторяющиеся значения. Это можно расширить, используя реализацию BinarySearch, которая возвращает список всех узлов с заданным значением вместо одного узла. Затем алгоритм может повторить этот список и оценить поддерево для каждого узла, а затем продолжить работу в обычном режиме.

Время выполнения этого алгоритма составляет O(n log m) (он пересекает n узлов в первом дереве и выполняет операцию бинарного поиска log m для каждого из них), что ставит его в один ряд с наиболее распространенными алгоритмами сортировки. Сложность пространства составляет O(1) во время работы (ничего не выделяется за исключением нескольких временных переменных) и O(n), когда он возвращает свой результат (потому что он создает явную копию поддерева, что может не потребоваться в зависимости от того, как именно работает алгоритм должен выразить свой результат). Таким образом, даже этот грубый метод должен работать достаточно хорошо, хотя, как отмечалось в других ответах, возможно решение O(n).

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

Answer 3

Следующий алгоритм вычисляет все самые большие общие поддеревья двух двоичных деревьев (без предположения, что это двоичное дерево поиска).Пусть S и T два двоичных дерева.Алгоритм работает снизу вверх, начиная с листьев.Начнем с определения листьев с одинаковым значением.Затем рассмотрите их родителей и определите узлы с теми же детьми.В более общем смысле на каждой итерации мы идентифицируем узлы при условии, что они имеют одинаковое значение, а их дочерние элементы изоморфны (или изоморфны после замены левого и правого дочерних элементов).Этот алгоритм заканчивается набором всех пар максимальных поддеревьев в T и S.

Вот более подробное описание:

Пусть S и T - два двоичных дерева.Для простоты можно предположить, что для каждого узла n левый потомок имеет значение <= правый потомок.Если ровно один дочерний элемент узла n равен NULL, мы предполагаем, что правый узел равен NULL.(В общем, мы считаем два поддерева изоморфными, если они с точностью до перестановки левого / правого потомка для каждого узла.) </p>

(1) Найти все листовые узлы в каждом дереве.

(2) Определите двудольный граф B с ребрами от узлов в S до узлов в T, изначально без ребер.Пусть R (S) и T (S) - пустые множества.Пусть R (S) _next и R (T) _next также будут пустыми наборами.

(3) Для каждого листового узла в S и каждого листового узла в T создайте ребро в B, если узлы имеют одинаковыезначение.Для каждого ребра, созданного от nodeS в S до nodeT в T, добавьте все родительские элементы nodeS к набору R (S) и все родительские узлы nodeT к набору R (T).

(4) Для каждого узла узла S в R (S) и каждого узла узла T в T (S), проведите ребро между ними в B, если они имеют одинаковое значение AND {(i): nodeS->left соединяется с nodeT-> left, а nodeS-> right соединяется с nodeT-> right, ИЛИ (ii): nodeS-> left соединяется с nodeT-> right, а nodeS-> right соединяется с nodeT-> left,ИЛИ (iii): nodeS-> left соединяется с nodeT-> right и nodeS-> right == NULL и nodeT-> right == NULL

(5) Для каждого ребра, созданного на шаге (4), добавьте их родителей к R (S) _next и R (T) _next.

(6) Если (R (S) _next) непусто {(i) поменяйте местами R (S) и R (S)_next и поменяйте местами R (T) и R (T) _next.
(ii) Очистите содержимое R (S) _next и R (T) _next.
(iii) Вернитесь к шагу (4).}

Когда этот алгоритм завершается, R (S) и T (S) содержат корни всех максимальных поддеревьев в S и T. Кроме того, двудольный граф B идентифицирует все пары узлов в S и узлов в Tкоторые дают изоморфные поддеревья.

Я полагаю, что этот алгоритм имеет сложность O (n log n), где n - общее количество узлов в S и T, поскольку наборы R (S) и T (S) могут храниться в BST.упорядоченный по значению, однако мне было бы интересно увидеть доказательство.

Answer 4

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

Алгоритм основан на динамическом программировании и работает со следующей интуицией: предположим, что у нас есть дерево T с корнем r и дочерними T1 и T2.Предположим, что другим деревом является S. Теперь предположим, что мы знаем максимальное общее поддерево T1 и S и T2 и S. Тогда максимальное поддерево T и S

1. полностью содержится в T1 иr.
2. полностью содержится в T2 и r.
3. Используются как T1, T2, так и r.

Следовательно, мы можем вычислить максимальное общее поддерево (Я сокращу это как MCS) следующим образом.Если MCS (T1, S) или MCS (T2, S) имеют корни T1 или T2 в качестве корней, то MCS, которую мы можем получить из T и S, дается большей из MCS (T1, S) и MCS (T2).S).Если ровно один из MCS (T1, S) и MCS (T2, S) имеет корень T1 или T2 в качестве корня (предположим, wlog, что это T1), то ищите r в S. Если r имеет корень T1 какребенок, тогда мы можем расширить это дерево узлом, а MCS задается большим из этого расширенного дерева и MCS (T2, S).В противном случае, если и MCS (T1, S), и MCS (T2, S) имеют корни T1 и T2 в качестве корней, то ищите r в S. Если у него есть потомок корня T1, мы можем расширить дереводобавив в т.Если у него есть дочерний корень T2, мы можем расширить это дерево, добавив в r.В противном случае мы просто берем большее из MCS (T1, S) и MCS (T2, S).

Формальная версия алгоритма выглядит следующим образом:

1. Создайте новыйХеш-таблица отображает узлы в дереве S от их значения до соответствующего узла в дереве.Затем заполните эту таблицу узлами S, выполнив стандартное обход дерева по времени O (m).
2. Создайте новые узлы отображения хеш-таблицы в T от их значения до размера максимального общего поддеревадерево укоренено в этом узле и S. Обратите внимание, что это означает, что MCS-ы, хранящиеся в этой таблице, должны быть непосредственно с корнем в данном узле.Оставьте эту таблицу пустой.
3. Создайте список узлов T, используя обход по порядку.Это занимает O (N) время.Обратите внимание, что это означает, что мы всегда будем обрабатывать все дочерние узлы перед самим узлом;это очень важно!
4. Для каждого узла v в обходе после заказа в порядке их посещения:
   1. Найдите соответствующий узел в хеш-таблице для узлов S.
   2. Если узел не был найден, установите размер MCS с корнем в v равным 0.
   3. Если узел S 'был найден в S:
      1. Если ни один из потомковv 'соответствует дочерним элементам v, установите размер MCS с корнем в v равным 1.
      2. Если точно один из дочерних элементов v' совпадает с дочерним элементом v, установите размер MCS с корнем в vдо 1 плюс размер MCS поддерева с корнем у этого потомка.
      3. Если оба потомка v 'совпадают с потомками v, установите размер MCS с корнем в v равным 1 плюс размерMCS левого поддерева плюс размер MCS правого поддерева.
5. (Обратите внимание, что шаг (4) выполняется в ожидаемом O (n)время, так как он посещает каждый узел в S ровно один раз, делает O (n) поиск хеш-таблицы, делает n вставок хеш-таблицы и делает ACпостоянное количество обработки на узел).
6. Выполните итерацию по хеш-таблице и верните максимальное значение, которое она содержит.Этот шаг занимает также O (n) времени.Если хеш-таблица пуста (S имеет нулевой размер), вернуть 0.

В целом, время выполнения составляет ожидаемое время O (n + m) и пространство O (n + m) для двух хешейтаблицы.

Чтобы увидеть доказательство корректности, мы будем индуцировать по высоте дерева T. В качестве базового случая, если T имеет нулевую высоту, мы просто возвращаем ноль, потому что цикл в (4) ничего не добавляет кхеш-таблица.Если T имеет высоту один, то либо он существует в T, либо его нет.Если он существует в T, то у него вообще не может быть дочерних элементов, поэтому мы выполняем ветку 4.3.1 и говорим, что она имеет высоту один.Шаг (6) затем сообщает, что MCS имеет размер один, который является правильным.Если он не существует, то мы выполняем 4.2, помещая ноль в хеш-таблицу, поэтому шаг (6) сообщает, что MCS имеет нулевой размер, как и ожидалось.

Для индуктивного шага предположим, что алгоритм работает длявсе деревья высотой k '

Уф!Это была огромная проблема.Я надеюсь, что это решение верное!

РЕДАКТИРОВАТЬ: Как было отмечено @jonderry, это найдет самый большой общий подграф из двухдеревья, а не крупнейшее общее полное поддерево.Однако вы можете ограничить работу алгоритма только тем, что работаете только с поддеревьями.Для этого вы должны изменить внутренний код алгоритма так, чтобы он записывал поддерево размера 0, если оба поддерева отсутствуют с ненулевым размером.Подобный индуктивный аргумент покажет, что это найдет наибольшее полное поддерево.

Хотя, по общему признанию, мне больше нравится проблема "самого большого общего подграфа".: -)