以下是SICP的练习2.65:
使用练习2.63和2.64的结果给出实现为(平衡)二叉树的集合的union-set和intersection-set的Θ(n)实现.
在"设置为有序列表"一章和练习2.62中,我们已经为有序列表设置了union-set和intersection-set.我在Internet上搜索过,2.65的答案太简单了,它们只是将二叉树转换成列表,仍然使用了有序列表的union-set和intersection-set.
在我看来,我们需要将集合转换为二叉树并重写二叉树的union-set和intersection-set.
那么,我是否误解了SICP练习2.65的含义？还是有一个很好的答案？
在这种情况下，“简单”的答案是正确的：通过首先将树转换为列表来解决练习（事实上，有序列表，因为我们正在对树进行中序遍历），然后使用有序集过程，最后将结果集返回到树中。为什么这是正确的？因为所描述的过程O(n)使用现有的过程实现了所需的复杂性 - 无需重新发明轮子！
虽然可以通过操作树来编写“直接”答案，但这太麻烦了，并且在不使用变异操作的情况下实现会非常棘手（如果不是不可能！）O(n)- 到目前为止，在书中，我们还没有使用过set!，set-car!或者set-cdr!。