我是否误解了练习2.65的意义？

Question

以下是国际预防犯罪中心的实践2.65：

使用练习2.63和2.64的结果给出作为(平衡)二叉树实现的集合的联合集和交集的Θ(n)实现。

在“集合为有序列表”一章和练习2.62中，我们已经为有序列表设置了联合集和交叉集。我在互联网上搜索过，2.65的答案太简单了，不能接受，他们只是把二叉树转换成列表，并且仍然使用联合集和交集来表示排序列表。

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

那么，我是否误解了SICP 2.65练习的意义？还是有一个很好的答案？

Answer 1

在这种情况下，“简单”的答案是正确的:这个练习是通过首先将树转换成列表来解决的(事实上，是有序列表，因为我们正在按顺序遍历树)，然后使用有序集过程，最后将得到的集合转换回树。为什么这是正确的？因为所描述的过程实现了所需的O(n)复杂性使用已经存在的过程-不需要重新发明车轮！

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

Answer 2

您是对的，您可以使用前面的文本示例来指导如何为平衡的二叉树编写高效的union-set和intersection-set实现。然而，文本显式地告诉您使用前两个练习的结果，因此它将指导您找到一个特定的解决方案。该解决方案(将二叉树转换为列表以将问题简化为已解决的问题)已经是O(n)，这是您可以从这个问题得到的最佳顺序。