合并两棵树集合

我想获得两个集合的联合。基本上二叉树（但不保证平衡）。这是代码：合并两棵树集合

class MyNonEmptySet extends MySet{ 

union(that: MyNonEmptySet): MySet = { 
    ((left union right) union that) incl elem 
    } 

} 

class MyEmptySet extends MySet{ 
    union(that: MyNonEmptySet): MySet = that  
}

对于小型数据集，工会工作正常，但当数据是一个大的，但是，工会不会再回到。它只是继续。我想了解发生了什么问题。如果它没有返回，它应该至少用尽内存（堆栈溢出异常），对吧？我该如何纠正这一点？

＃EDIT1

如果我改变paranthesis在NonEmptySet执行它的工作原理。

(left union (right union that)) incl elem

我不明白为什么？两者都应该给出相同的结果吗？为什么一种方法需要永久（但不会耗尽内存），另一种方法会立即为相同的数据工作？

来源

2017-08-06 Ashwin

二叉树是一个很好的数据结构的原因是它被排序，所以你可以在日志时间快速搜索。

看起来像你不使用排序的二叉树。

你的第二个算法的工作，但所有的工作都是由

incl elem

这是相当缓慢进行。

第一个算法有一个递归步骤，它正在执行它自己的联合，但它永远不会离开递归步骤。

在Scala中有很好的树集算法，我只会使用其中之一。

合并二叉树正确的方法是使用红黑树，但这是不平凡： https://www.wikiwand.com/en/Red%E2%80%93black_tree

来源

2017-08-06 05:53:36

“你的第二个算法的工作，但所有的工作都是由含ELEM完成”。你能否详细说明这一点？为什么第一个算法不适用于更大的数据集？我只想知道这些答案。无论如何，我会通过你正确的方式来合并二叉树的链接。 – Ashwin

我想说的是，不是有一个有效的递归算法做分而治之，合并的所有工作都将由include完成。这没有利用数据结构。 –

合并两棵树集合

回答

相关问题