如何找到最大的公共子树在给定的两个二进制搜索树？ [英] How to find largest common sub-tree in the given two binary search trees?

问题描述

二 BSTS （二叉搜索树）给出。如何找到最大的公共子树在给定的两个二叉树？

修改1： 以下是我曾想过：

让，R1 =当前第1树的节点      R2 =当前第二树的节点

 有一些我认为，我们需要考虑的情况：

案例1：r1.data＆LT; r2.data
     2子问题来解决：
     首先，检查R1和r2.left
     第二，检查r1.right和r2

案例2：r1.data＆GT; r2.data
     2子问题来解决：
        - 首先，检查r1.left和r2
        - 第二，检查R1和r2.right

案例3：r1.data == r2.data
     此外，有2例在这里考虑：
     （一）当前节点是最大的共同BST部分
         计算公共子树的大小扎根在R1和R2
     （二）当前节点是不是最大的共同BST部分
         2子问题来解决：
         第一，解决r1.left和r2.left
         第二，解决r1.right和r2.right
 

我能想到的，我们需要检查的情况下，但我不能够code是，截至目前。它不是一门功课的问题。像不像？

解决方案

刚刚散列孩子，每个节点的关键，查找重复。这将使一个线性预期时间算法。例如，请参见下面的伪code，假设不存在哈希冲突（涉及碰撞将是直接的）：

  RET = -1
// T是树节点，H是一个哈希集，第一个是布尔标志
hashTree（T，H，在前）：
  如果（T为null）：
    返回0 //叶案
  H =散列（hashTree（T.left，H，第一），hashTree（T.right，H，第一），T.key）
  如果（第一）：
    //为T1的节点的集合H存储散列
    H.insert（H）
  其他：
    //检查的T2的节点包含T1的节点的集合H散列
    如果H.contains（H）：
      RET = MAX（RET，尺寸（T））//大小是递归memoized得到O（n）的总时间
  回^ h

H = {}
hashTree（T1，H，真）
hashTree（T2，H，FALSE）
返回RET
 

请注意，这是假设BST的子树的标准定义，即子树由节点及其所有后代。

Two BSTs (Binary Search Trees) are given. How to find largest common sub-tree in the given two binary trees?

EDIT 1: Here is what I have thought:

Let, r1 = current node of 1st tree r2 = current node of 2nd tree

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

I can think of the cases we need to check, but I am not able to code it, as of now. And it is NOT a homework problem. Does it look like?

解决方案

Just hash the children and key of each node and look for duplicates. This would give a linear expected time algorithm. For example, see the following pseudocode, which assumes that there are no hash collisions (dealing with collisions would be straightforward):

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

Note that this is assuming the standard definition of a subtree of a BST, namely that a subtree consists of a node and all of its descendants.

这篇关于如何找到最大的公共子树在给定的两个二进制搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！