合併兩棵樹集合

我想獲得兩個集合的聯合。基本上二叉樹（但不保證平衡）。這是代碼：合併兩棵樹集合

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完成。這沒有利用數據結構。 –

合併兩棵樹集合

回答

相關問題