scheme - 我是否误解了 SICP 练习 2.65 的含义？

Question

这是 SICP 的练习 2.65:

Use the results of exercises 2.63 and 2.64 to give Θ(n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

在“集合作为有序列表”一章和练习 2.62 中，我们已经有了有序列表的并集和交集。我在网上搜了一下，2.65的答案太简单了，无法接受，他们只是将二叉树转换为列表，并且仍然使用并集和交集作为有序列表。

在我看来，我们需要将集合转换为二叉树，并重写二叉树的并集和交集。

那么，我是否误解了SICP练习2.65的含义？或者有什么好的答案吗？

Answer 1

在这种情况下，“简单”的答案是正确的:通过首先将树转换为列表(实际上，有序列表，因为我们正在对树进行中序遍历)来解决该练习，然后使用有序集过程，最后将结果集转换回树。为什么这是正确的？因为所描述的过程使用现有过程实现了所需的 O(n) 复杂性 - 无需重新发明轮子!

虽然可以通过操作树来编写“直接”答案，但这太麻烦了，而且在 O(n) 中实现会非常棘手(如果不是不可能的话!)不使用变异操作 - 到目前为止，在本书中，我们还没有使用 set!、set-car! 或 set-cdr!.