我誤解了SICP練習2.65的含義嗎？

Question

這裏是SICP行使2.65：

使用的練習2.63和2.64的成績給予Θ（n）的實現工會集，並且對爲（平衡）二叉樹實現集合交叉點設置。

在「設置爲有序列表」和練習2.62的章節中，我們已經爲有序列表設置了聯合集和交集。我搜索了互聯網，2.65的答案太簡單了，他們只是將二叉樹轉換爲列表，並仍然使用聯合集和交集爲有序列表設置。

在我看來，我們需要將這些集合轉換爲二叉樹，並重寫二叉樹的聯合集和交集。

那麼，我誤解了SICP練習2.65的含義嗎？還是有一個很好的答案？

Answer 1

「簡單」的答案是在這種情況下，正確的：鍛鍊時，首先轉換成樹列表（事實上，下令名單，因爲我們正在做的序樹的遍歷），然後使用ordered-解決設置程序，最後將結果集轉換回樹。爲什麼這是正確的？因爲所描述的程序使用已有的程序實現了所需的複雜性 - 無需重新發明輪子！

儘管可以通過操縱樹來編寫「直接」答案，但它太麻煩了，而且要在O(n)中實施而不使用變異操作會非常棘手（如果不是不可能的話）在本書中，我們尚未使用set!,set-car!或set-cdr!。

Answer 2

你是對的，你可能使用文本的早期例子作爲編寫平衡二叉樹的union-set和intersection-set的高效實現的指南。然而，文本明確地告訴你使用前面兩個練習的結果，所以它引導你走向一個特定的解決方案。該解決方案（將二叉樹轉換爲列表以將問題簡化爲已解決的問題）已經是O（n），無論如何，這是最好的順序。