这是 SICP 的练习 2.65：
使用练习 2.63 和 2.64 的结果，给出实现为（平衡）二叉树的集合的并集和交集的 Θ(n) 实现。
在“集合为有序列表”一章和练习 2.62 中，我们已经有了有序列表的并集和交集。我在网上搜索过，2.65 的答案太简单了，无法接受，他们只是将二叉树转换为列表，仍然使用并集和交集作为有序列表。
在我看来，我们需要将集合转换为二叉树，并重写二叉树的并集和交集。
那么，我是不是误解了 SICP 练习 2.65 的含义呢？或者有什么好的答案吗？
问问题
412 次
2 回答
3
在这种情况下，“简单”的答案是正确的：首先将树转换为列表（实际上是有序列表，因为我们正在对树进行中序遍历），然后使用有序集过程，最后转换结果集回到树中。为什么这是正确的？因为所描述的程序使用已经存在的程序实现了所需的O(n)复杂性 - 无需重新发明轮子！
尽管可以通过操纵树来编写“直接”答案，但这太麻烦了，而且在不使用变异操作的情况下实现起来会非常棘手（如果不是不可能的话！）O(n)——直到本书中的这一点，我们还没有使用set!，set-car!或者set-cdr!。
于 2013-07-08T13:43:09.937 回答
2
你是对的，你可以使用文本中较早的示例作为编写平衡二叉树的有效实现union-set的指南。intersection-set但是，文本明确告诉您使用前两个练习的结果，因此它会引导您找到特定的解决方案。该解决方案（将二叉树转换为列表以将问题减少为已解决的问题）已经是 O(n)，无论如何这是您可以解决此问题的最佳顺序。
于 2013-07-08T15:03:21.507 回答