海量数据:判断一棵树是否为另一棵树的子树
海量数据:判断一棵树是否为另一棵树的子树
一贱书生 发表于1年前
海量数据:判断一棵树是否为另一棵树的子树
  • 发表于 1年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

     T1是一棵含有几百万个节点的树,T2含有几百个节点。判断T2是否是T1 的子树。

首先考虑小数据量的情况,可以根据树的前序和中序遍历所得的字符串,来通过判断T2生成的字符串是否是T1字符串的子串,来判断T2是否是T1的子树。假设T1的节点数为N,T2的节点数为M。遍历两棵树算法时间复杂性是O(N + M), 判断字符串是否为另一个字符串的子串的复杂性也是O( N + M)(比如使用KMP算法)。所需要的空间也是O(N + M)。

这里有一个问题需要注意:对于左节点或者右节点为null的情况,需要在字符串中插入特殊字符表示。否则对于下面这种情形将会判断错误:

因此如果插入特殊字符,上述两棵树的中序和前序遍历的结果是相同的。

由于本例有几百万的节点,需要占用O(N + M)的内存。

如果换一种思路,就是遍历T1,每当T1的某个节点与T2的根节点值相同时,就判断两棵子树是否相同。这个算法的复杂度是O(N*M)。我们再仔细 思考一下。因为只有在节点值与T2的根节点值相同才会调用O(M)。假设有K次这种情况,那么算法的复杂度就是O(N + K*M)。

  1. package Tree_Graph;  
  2.   
  3. import CtCILibrary.AssortedMethods;  
  4. import CtCILibrary.TreeNode;  
  5.   
  6. public class S4_8 {  
  7.   
  8.     // 判断t2是否是t1的子树  
  9.     public static boolean isSubTree(TreeNode t1, TreeNode t2) {  
  10.         if(t2 == null) {            // 空树始终是另一个树的子树  
  11.             return true;  
  12.         }  
  13.         if(t1 == null) {        // 此时r2非空,非空树不可能是一个空树的子树  
  14.             return false;  
  15.         }  
  16.         if(t1.data == t2.data) {            // 找到两树匹配  
  17.             if(isSameTree(t1, t2)){  
  18.                 return true;  
  19.             }  
  20.         }  
  21.           
  22.         // 继续在r1的左子树和右子树里找匹配  
  23.         return isSubTree(t1.left, t2) || isSubTree(t1.right, t2);  
  24.     }  
  25.       
  26.     // 判断两棵树是否相同  
  27.     public static boolean isSameTree(TreeNode t1, TreeNode t2) {  
  28.         if(t1==null && t2==null) {  
  29.             return true;  
  30.         }  
  31.         if(t1==null || t2==null) {  
  32.             return false;  
  33.         }  
  34.           
  35.         if(t1.data != t2.data) {  
  36.             return false;  
  37.         }  
  38.         return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);  
  39.     }  
  40.       
  41.     public static void main(String[] args) {  
  42.         // t2 is a subtree of t1  
  43.         int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};  
  44.         int[] array2 = {2, 4, 5, 8, 9, 10, 11};  
  45.   
  46.         TreeNode t1 = AssortedMethods.createTreeFromArray(array1);  
  47.         TreeNode t2 = AssortedMethods.createTreeFromArray(array2);  
  48.   
  49.         if (isSubTree(t1, t2))  
  50.             System.out.println("t2 is a subtree of t1");  
  51.         else  
  52.             System.out.println("t2 is not a subtree of t1");  
  53.   
  54.         // t4 is not a subtree of t3  
  55.         int[] array3 = {1, 2, 3};  
  56.         TreeNode t3 = AssortedMethods.createTreeFromArray(array1);  
  57.         TreeNode t4 = AssortedMethods.createTreeFromArray(array3);  
  58.   
  59.         if (isSubTree(t3, t4))  
  60.             System.out.println("t4 is a subtree of t3");  
  61.         else  
  62.             System.out.println("t4 is not a subtree of t3");  
  63.     }  
  64. }

 

 

 

对于上面讨论的2种解法,哪种解法比较好呢?其实有必要好好讨论一番:

1)方法一会占用O(N + M)的内存,而另外一种解法只会占用O(logN + logM)的内存(递归的栈内存)。当考虑scalability扩展性时,内存使用的多寡是个很重要的因素。

2)方法一的时间复杂度为O(N + M),方法二最差的时间复杂度是O(N*M)。所以要通过工程实践或者是历史数据看一下哪种方法更优。当然了,方法二也可能会很早发现两棵树的不同,早早的退出了checkSubTree。

总的来说,在空间使用上,方法二更好。在时间上,需要通过实际数据来验证。

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 17
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: