SICP の演習 2.65 は次のとおりです。
演習 2.63 と 2.64 の結果を使用して、(平衡) 二分木として実装された集合の和集合と交差集合の Θ(n) 実装を与えます。
「順序付きリストとしての集合」の章と演習 2.62 では、順序付きリストの和集合と交差集合が既にあります。私はインターネットを検索しました.2.65の答えは単純すぎて受け入れることができません.2分木をリストに変換するだけで、順序付きリストにはunion-setとintersection-setを使用しています.
私の意見では、セットをバイナリ ツリーに変換し、バイナリ ツリーの和集合と交差セットを書き直す必要があります。
では、SICP の演習 2.65 の意味を誤解しているのでしょうか? それとも良い答えはありますか？
この場合、「単純な」答えは正しいです: 演習は、最初にツリーをリストに変換することによって解決されます (実際には、ツリーを順番に走査しているため、順序付きリストになります)。次に、順序集合手続きを使用し、最後に変換します。結果のセットはツリーに戻ります。なぜこれが正しいのですか？O(n)説明されている手順は、既存の手順を使用して必要な複雑さを実現するため、車輪を再発明する必要はありません。
ツリーを操作することで「直接的な」答えを書くことはできますが、それは面倒であり、O(n)突然変異操作を使用せずに実装するのは非常に困難です (不可能ではないにしても!)。 set!、set-car!またははまだ使用していませんset-cdr!。
おっしゃる通り、バランスの取れたバイナリ ツリーの効率的な実装を作成するためのガイドとして、テキストの前の例を使用できます。ただし、このテキストでは、前の 2 つの演習の結果を使用するように明示的に指示されているため、特定の解決策へと導かれています。その解決策 (二分木をリストに変換して問題を既に解決済みのものに減らす) は既に O(n) であり、とにかくこの問題で得られる最良の順序です。union-setintersection-set