如何在给定的两个二叉搜索树中找到最大的公共子树？

Question

如何在给定的两个二叉搜索树中找到最大的公共子树？

17

给定两个二叉搜索树（BSTs），如何找到它们的最大公共子树？

编辑1： 这是我的想法：

令 r1 为第一个树的当前节点 r2 为第二个树的当前节点

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

我可以想到需要检查的情况，但现在我无法编写代码。这不是一道作业题。看起来怎么样？

- Bhushan

这是作业吗？你尝试过什么？哪些有效，哪些无效？ - Konerak

Konerak: 刚刚编辑了问题，请看一下。并且这不是作业。 Nayuki: 我不知道为什么答案会有用，但这是一个问题。而且既然它是BST，我很确定某个应用程序的某个部分一定在使用它。 :) - Bhushan

你的算法复杂度是多少？ - letsc

你不能只是对两棵树进行中序遍历，将节点值存储到某个数组中，然后找到最长公共子序列吗？？虽然，我猜复杂度最终会变成O(n²)。 - letsc

1

有趣的是，下面的两个答案除了节点都具有唯一标签这一事实之外，都没有利用到树是BST的事实。我想知道是否有更快的算法可以利用这个事实？ - templatetypedef

显示剩余2条评论

4个回答

3

假设树中没有重复的值：

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

简单来说，这是一个暴力解决问题的方法。它对第一棵树进行广度优先遍历。对于每个节点，它在第二棵树中执行二分查找以找到相应的节点。然后使用这些节点计算以它们为根的公共子树的总大小。如果子树比之前发现的任何子树都大，则将其记住以便在算法完成时构造并返回最大子树的副本。

此算法不处理重复值。可以通过使用返回具有给定值的所有节点列表而不仅仅是单个节点的二分查找实现来扩展它。然后算法可以迭代此列表并为每个节点评估子树，然后按照正常方式继续。

该算法的运行时间为O(n log m)（它遍历第一棵树中的n个节点，并为每个节点执行log m个二分搜索操作），与大多数常见排序算法相当。运行时空间复杂度为O(1)（除了一些临时变量外没有分配任何东西），并且在返回结果时为O(n)（因为它创建了子树的显式副本，具体取决于算法如何表示其结果）。因此，即使是这种暴力方法也应该表现得相当好，尽管如其他答案所指出的那样，O(n)的解决方案是可能的。

此算法还可以应用可能的优化，例如跳过任何包含在先前评估的子树中的节点。因为树遍历是广度优先的，我们知道任何先前某个子树的一部分的节点永远无法成为更大子树的根。这可以显着提高算法在某些情况下的性能，但最坏情况下的运行时间（两棵没有共同子树的树）仍然为O(n log m)。

- aroth

1

请问您能否简要解释一下您的算法？ - Bhushan

好极了.. :) 把指向遇到最大共同子树的子树根节点的指针存储起来不是很有好处吗？ - letsc

@10101010 - 添加了解释。 - aroth

@smartmuki - 是的，这将修剪掉重复的BinarySearch操作，或者如果算法不需要隔离并返回最大公共子树的副本，则可以直接作为结果返回。 - aroth

1

@aroth：算法看起来没问题，但你说的复杂度O(n log m)听起来不对。你将首先逐个遍历第一棵树的节点，所以这是O(n)。这是正确的。但是一旦你在第二棵树中进行了BinarySearch并找到了相应的节点，从那时起你又必须再次逐个匹配节点。因此，你将在log n * n时间内遍历第二棵树，这将是O(n)。因此总复杂度将为O(n ^ 2)（第一棵树为O(n)，第二棵树为O(n)）。 - Bhushan

1

我相信我有一个O(n+m)时间复杂度，O(n+m)空间复杂度的算法来解决这个问题，假设树的大小分别为n和m。该算法假设树中的值是唯一的（即每个元素最多在每棵树中出现一次），但它们不需要是二叉搜索树。

该算法基于动态规划，并具有以下直觉：假设我们有一棵根为r，子树为T1和T2的树T。假设另一棵树为S。现在，假设我们知道T1和S的最大公共子树以及T2和S的最大公共子树。那么T和S的最大子树

完全包含在T1和r中。
完全包含在T2和r中。
同时使用T1、T2和r。

因此，我们可以按照以下方式计算最大公共子树（简称 MCS）。如果 MCS(T1, S) 或 MCS(T2, S) 其中一个的根是 T1 或 T2 的根，则从 T 和 S 中得到的 MCS 是由 MCS(T1, S) 和 MCS(T2, S) 中较大的那个给出的。如果仅有 MCS(T1, S) 和 MCS(T2, S) 中的一个具有 T1 或 T2 的根作为根（假设 w.l.o.g. 是 T1），则在 S 中查找 r。如果 r 有 T1 的根作为子节点，则我们可以通过添加一个节点来扩展该树，并且 MCS 给出的是这个增强树和 MCS(T2, S) 中较大的那个。否则，如果 MCS(T1, S) 和 MCS(T2, S) 都具有 T1 和 T2 的根作为根，则在 S 中查找 r。如果它有 T1 的根作为子节点，我们可以通过添加 r 来扩展树。如果它有 T2 的根作为子节点，我们可以通过添加 r 来扩展该树。否则，我们只需取 MCS(T1, S) 和 MCS(T2, S) 中较大的那个。

算法的正式版本如下：

创建一个新的哈希表，将树S中的节点从其值映射到树中相应的节点。然后通过标准的树遍历在O(m)时间内填充此表与S的节点。
创建一个新的哈希表，将T中的节点从它们的值映射到以该节点为根的树和S的最大公共子树的大小。请注意，这意味着存储在此表中的MCS必须直接根据给定节点进行。保留此表为空。
使用后序遍历创建T的节点列表。这需要O(n)时间。请注意，这意味着我们将始终在处理节点本身之前处理所有节点的子节点；这非常重要！
对于后序遍历中按访问顺序的每个节点v：
1. 查找S节点哈希表中相应的节点。
2. 如果未找到节点，则将以v为根的MCS的大小设置为0。
3. 如果在S中找到了节点v'：
  1. 如果v'的任何一个子节点都不匹配v的子节点，则将以v为根的MCS的大小设置为1。
  2. 如果v'的一个子节点恰好匹配v的一个子节点，则将以v为根的MCS的大小设置为1加上以该子节点为根的子树的MCS的大小。
  3. 如果v'的两个子节点都匹配v的子节点，则将以v为根的MCS的大小设置为1加上左子树和右子树的MCS的大小。
（请注意，步骤（4）的运行时间预期为O(n)，因为它仅访问S中的每个节点一次，进行O(n)哈希表查找，进行n个哈希表插入，并对每个节点进行恒定数量的处理）。
遍历哈希表并返回其包含的最大值。此步骤也需要O(n)时间。如果哈希表为空（S的大小为零），则返回0。

总的来说，运行时间预期为O(n + m)，两个哈希表的空间也是O(n + m)。

为了证明正确性，我们通过对树T的高度进行归纳来进行。作为基本情况，如果T的高度为零，则我们只返回零，因为（4）中的循环不会向哈希表中添加任何内容。如果T的高度为一，则它存在于T中或不存在于T中。如果它存在于T中，则它不能有任何子节点，因此我们执行分支4.3.1并说它的高度为一。然后步骤（6）报告MCS的大小为一，这是正确的。如果它不存在，则我们执行4.2，将零放入哈希表中，因此步骤（6）报告MCS的大小为零，正如预期的那样。

在归纳步骤中，假设该算法适用于所有高度为k'

哇！这是一个很棒的问题。我希望这个解决方案是正确的！

编辑：正如@jonderry所指出的那样，这将找到两棵树的最大公共子图，而不是最大公共完整子树。但是，您可以很容易地限制算法仅在子树上工作。为此，您将修改算法的内部代码，以便仅在两个子树都不存在非零大小的情况下记录大小为0的子树。类似的归纳论证将表明，这将找到最大的完整子树。

尽管如此，我确实更喜欢“最大公共子图”问题。 :-)

- templatetypedef

templatetypedef，你觉得如果我们利用它是二叉搜索树这个事实，解决方案会变得非常简化吗？ - Bhushan

在你的算法中，对于步骤1，"从它们的值到树中相应节点的对应位置"是什么意思？你是想要存储该值和位置（例如层级、左/右差异）吗？能给一个例子吗？在步骤2中，如何预先确定子树的大小？我们不知道它会是多少。而且，元素在哈希表中存储的顺序是不固定的。如果顺序不同而节点相同，则树不会等于/是另一棵树的子树。 - Bhushan

@10101010- 可能可以简化这个过程，但我不确定如何做。哈希表将第二个BST中节点的键映射到节点本身，这使我们能够快速找到第二棵树中与第一棵树中的节点对应的节点（如果存在），并且此哈希表中节点的顺序在此算法中从未使用。在步骤2中，我们实际上还没有存储子树的大小；我们只是创建了一个空的哈希表，在第4部分的循环中填充它。这回答了你的问题吗？还是有其他需要我澄清的地方吗？ - templatetypedef

如果MCS（T1，S）或MCS（T2，S）具有T1或T2作为根，则将返回的根声明为root_T1或root_T2无法保证结果。我认为应该是“如果MCS（T1，S）或MCS（T2，S）具有S的根”。 - q0987

1

以下算法计算两个二叉树的所有最大公共子树（不假定它是二叉搜索树）。设S和T为两个二叉树。该算法从树的底部开始，从叶节点开始工作。我们首先识别具有相同值的叶子节点。然后考虑它们的父节点并识别具有相同子节点的节点。更一般地，在每次迭代中，只要它们具有相同的值且其子节点是同构的（或在交换左右子节点后同构），就会识别节点。此算法以T和S中所有最大子树对的集合终止。

以下是更详细的描述：

设S和T为两个二叉树。为简单起见，我们可以假设对于每个节点n，左子节点的值<=右子节点的值。如果节点n的一个子节点恰好为NULL，则假设右节点为NULL。（通常，我们认为如果它们对于每个节点的左/右子节点进行置换，则两个子树同构。）

(1) 找到每棵树中的所有叶节点。

（2）定义一个二分图B，从节点S到节点T的边缘，最初没有边缘。让R（S）和T（S）为空集。让R（S）_next和R（T）_next也是空集。

（3）对于S中的每个叶节点和T中的每个叶节点，如果节点具有相同的值，则在B中创建一条边缘。对于从S中的nodeS创建的每个边缘到T中的nodeT，将nodeS的所有父节点添加到集合R（S）中，并将nodeT的所有父节点添加到集合R（T）中。

（4）对于R（S）中的每个节点nodeS和T（S）中的每个节点nodeT，在它们之间绘制边缘，如果它们具有相同的值，并且 { （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 中节点的总数，因为可以通过值排序的 BST 存储 R(S) 和 T(S) 集合，但我很想看到一个证明。

- AH10

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jonderry · Accepted Answer

只需对每个节点的子节点和键进行哈希并查找重复项。这将提供一个线性预期时间算法。例如，看下面的伪代码，假设没有哈希冲突（处理冲突将很简单）：

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

请注意，这是基于二叉搜索树子树的标准定义假设，即一个子树由一个节点及其所有后代组成。