Как найти наибольшее общее поддерево в данных двух двоичных деревьях поиска?
Даны два BSTs
(Деревья двоичного поиска). Как найти наибольшее общее поддерево в данных двух binary trees
?
РЕДАКТИРОВАТЬ 1:
Вот что я подумал:
Пусть, r1 = текущий node 1-го дерева r2 = текущий node второго дерева
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
Я могу подумать о случаях, которые нам нужно проверить, но я не могу его закодировать, на данный момент. И это НЕ домашняя проблема. Это похоже?
Ответы
Ответ 1
Просто хешируйте детей и клавишу каждого node и ищите дубликаты. Это даст алгоритм линейного ожидаемого времени. Например, см. Следующий псевдокод, предполагающий, что не существует хеш-коллизий (рассмотрение столкновений было бы простым):
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 nodes in the set H
H.insert(h)
else:
// check for hashes of T2 nodes in the set H containing T1 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, а именно, что поддерево состоит из node и всех его потомков.
Ответ 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
Чтобы кратко объяснить, это решение проблемы грубой силы. Он делает первую прогулку первого дерева. Для каждого node он выполняет BinarySearch
второго дерева, чтобы найти соответствующий node в этом дереве. Затем, используя эти узлы, он вычисляет общий размер общего поддерева, внедренного там. Если поддерево больше любого ранее найденного поддерева, оно запоминает его позже, чтобы он мог построить и вернуть копию самого большого поддерева при завершении алгоритма.
Этот алгоритм не обрабатывает повторяющиеся значения. Это можно расширить, используя реализацию BinarySearch
, которая возвращает список всех узлов с заданным значением, а не только один node. Затем алгоритм мог бы перебирать этот список и оценивать поддерево для каждого node, а затем действовать как обычно.
Время работы этого алгоритма O(n log m)
(оно пересекает узлы n
в первом дереве и выполняет двоичную операцию поиска log m
для каждого из них), помещая его наравне с наиболее распространенными алгоритмами сортировки. Сложность пространства O(1)
во время работы (ничего не выделяется за пределами нескольких временных переменных) и O(n)
, когда она возвращает свой результат (поскольку она создает явную копию поддерева, которая может не потребоваться в зависимости от того, как именно алгоритм должен выразить свой результат). Поэтому даже этот подход с грубой силой должен выполняться достаточно хорошо, хотя, как отмечено другими ответами, возможно решение O(n)
.
Существуют также возможные оптимизации, которые могут быть применены к этому алгоритму, такие как пропускание любых узлов, которые содержались в ранее оцененном поддереве. Поскольку древовидная структура является первой, мы знаем, чем любой node, который был частью некоторого предшествующего поддерева, никогда не может быть корнем большего поддерева. Это может значительно повысить производительность алгоритма в некоторых случаях, но в худшем случае (два дерева без общих поддеревьев) все равно будет O(n log m)
.
Ответ 3
Я считаю, что для решения этой проблемы у меня есть O (n + m) -time, O (n + m) пространственный алгоритм, предполагая, что деревья имеют размер n и m соответственно. Этот алгоритм предполагает, что значения в деревьях уникальны (т.е. Каждый элемент появляется в каждом дереве не чаще одного раза), но они не должны быть двоичными деревьями поиска.
Алгоритм основан на динамическом программировании и работает со следующей интуицией: предположим, что мы имеем некоторое дерево T с корнем r и дочерними T1 и T2. Предположим, что другое дерево - S. Теперь предположим, что мы знаем максимальное общее поддерево T1 и S и T2 и S. Тогда максимальное поддерево T и S
- полностью содержится в T1 и r.
- Полностью содержится в T2 и r.
- Использует как 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 как потом мы можем расширить это дерево на node, а MCS задается большим размером этого расширенного дерева и MCS (T2, S). В противном случае, если оба MCS (T1, S) и MCS (T2, S) имеют корни T1 и T2 в качестве корней, то посмотрите на r в S. Если он имеет в качестве корня корень T1, мы можем расширить дерево добавив в r. Если он имеет в качестве корня корень T2, мы можем расширить это дерево, добавив в r. В противном случае мы просто возьмем больше MCS (T1, S) и MCS (T2, S).
Формальная версия алгоритма такова:
- Создать новую таблицу хеш-таблицы, отображающую узлы в дереве S от их значения до соответствующего node в дереве. Затем заполните эту таблицу узлами S, выполнив стандартный ход дерева в O (m) времени.
- Создайте новую таблицу хеш-таблицы, отображающую узлы в T от их значения до размера максимального общего поддерева дерева, корневого в этом node и S. Обратите внимание, что это означает, что MCS-es, хранящиеся в этой таблице, должны быть напрямую, внедренный в данный node. Оставьте эту таблицу пустой.
- Создайте список узлов T, используя обход послепорядка. Это занимает время O (n). Обратите внимание, что это означает, что мы всегда будем обрабатывать все дочерние элементы node до самого node; это очень важно!
- Для каждого node v в обход послепорядка в том порядке, в котором они были посещены:
- Посмотрите соответствующий node в хеш-таблице для узлов S.
- Если не найдено node, установите размер MCS, установленный в v, равным 0.
- Если a node v 'был найден в S:
- Если ни один из дочерних элементов v 'не соответствует дочерним элементам из v, установите размер MCS с корнем в v до 1.
- Если только один из дочерних элементов v 'соответствует дочернему элементу v, задайте размер MCS, внедренный в v, равный 1, плюс размер MCS поддерева, корневого для этого дочернего элемента.
- Если оба дочерних элемента v 'соответствуют дочерним элементам v, задайте размер MCS, внедренный в v, равный 1, плюс размер MCS левого поддерева плюс размер MCS правого поддерева.
- (Обратите внимание, что шаг (4) выполняется в ожидаемое время O (n), так как он посещает каждый node в S ровно один раз, выполняет поиск хэш-таблиц O (n), делает n вставки хэш-таблицы и делает константу количество обработки за node).
- Перейдите в хэш-таблицу и верните максимальное значение, которое оно содержит. Этот шаг также занимает время O (n). Если хэш-таблица пуста (S имеет нулевой размер), верните 0.
В целом, время выполнения - это время ожидания O (n + m) и O (n + m) для двух хэш-таблиц.
Чтобы убедиться в правильности доказательства, мы продолжаем индукцией по высоте дерева Т. В качестве базового случая, если T имеет высоту ноль, то мы просто возвращаем ноль, потому что цикл в (4) ничего не добавляет к хеш-таблица. Если T имеет высоту один, то либо он существует в T, либо нет. Если он существует в T, то он не может иметь никаких детей вообще, поэтому мы выполняем ветку 4.3.1 и говорим, что она имеет высоту. Шаг (6) затем сообщает, что MCS имеет размер один, что является правильным. Если он не существует, то мы выполняем 4.2, помещая нуль в хеш-таблицу, поэтому шаг (6) сообщает, что MCS имеет нулевой размер.
Для индуктивного шага предположим, что алгоритм работает для всех деревьев с высотой k ' k и рассмотрим дерево высоты k. Во время нашего почтового перехода из T мы будем посещать все узлы в левом поддереве, затем в правом поддереве и, наконец, корень T. По индуктивному предположению таблица значений MCS будет правильно заполнена для левой поддерево и правое поддерево, поскольку они имеют height & le; k - 1 < к. Теперь рассмотрим, что происходит, когда мы обрабатываем корень. Если корень не появляется в дереве S, тогда мы помещаем в таблицу нуль, а шаг (6) выбирает самое большое значение MCS некоторого поддерева T, которое должно быть полностью включено либо в его левое поддерево, либо вправо поддерево. Если корень появляется в S, то мы вычисляем размер MCS, внедренный в корень T, пытаясь связать его с MCS-es его двух детей, которые (индуктивно!) Мы вычислили правильно.
Уф! Это была потрясающая проблема. Надеюсь, это решение будет правильным!
EDIT: Как было отмечено @jonderry, это найдет самый большой общий подграф двух деревьев, а не самый большой общий полный поддерево. Тем не менее, вы можете ограничить алгоритм просто работать на поддеревьях довольно легко. Для этого вы должны изменить внутренний код алгоритма так, чтобы он записывал поддерево размера 0, если оба поддерева не имеют ненулевого размера. Аналогичный индуктивный аргумент покажет, что это найдет наибольшее полное поддерево.
Хотя, по общему признанию, мне больше нравится проблема "самый большой общий подграф".: -)
Ответ 4
Следующий алгоритм вычисляет все самые большие общие поддеревья двух бинарных деревьев (без предположения, что это двоичное дерево поиска). Пусть S и T - два бинарных дерева. Алгоритм работает со дна деревьев вверх, начиная с листьев. Начнем с определения листьев с одинаковым значением. Затем рассмотрите их родителей и определите узлы с теми же детьми. В более общем плане на каждой итерации мы идентифицируем узлы при условии, что они имеют одинаковое значение, а их дети изоморфны (или изоморфны после замены левого и правого детей). Этот алгоритм заканчивается совокупностью всех пар максимальных поддеревьев в T и S.
Вот более подробное описание:
Пусть S и T - два бинарных дерева. Для простоты можно предположить, что для каждого node n левый дочерний элемент имеет значение <= правильный ребенок. Если ровно один ребенок из node n равен NULL, мы предполагаем, что правый node равен NULL. (В общем случае мы рассматриваем два поддеревья, изоморфные, если они соответствуют перестановке левых/правых детей для каждого node.)
(1) Найдите все листовые узлы в каждом дереве.
(2) Определите двудольный граф B с ребрами из узлов в S в узлы в T, изначально без ребер. Пусть R (S) и T (S) - пустые множества. Пусть R (S) _next и R (T) _next также являются пустыми множествами.
(3) Для каждого листа node в S и каждого листа node в T создайте ребро в B, если узлы имеют одинаковое значение. Для каждого ребра, созданного от nodeS в S до nodeT в T, добавьте все родители узла S в набор R (S) и все родители узла T к множеству R (T).
(4) Для каждого узла node в R (S) и каждого узла node nodeT в T (S) нарисуйте ребро между ними в B, если они имеют одинаковое значение AND
{ (i): nodeS- > left подключен к nodeT- > left, а nodeS- > right подключен к nodeT- > right, OR (ii): nodeS- > left подключен к nodeT- > right, а nodeS- > right подключен к nodeT- > left, OR (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 и swap 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, упорядоченных по значению, однако мне было бы интересно увидеть доказательство.