Note
为了避免和所使用的辅助程序发生重名冲突,本题的 intersection-set
被改名为 intersection-tree
, union-set
被改名成 union-tree
。
使用树实现的 \(\Theta(n)\) 复杂度的 intersection-tree
和 union-tree
的步骤如下:
tree->list-2
程序,将输入的两棵树转换成两个列表,复杂度 \(\Theta(n)\) 。intersection-set
计算两个列表的交集;如果要执行的是并集操作,那么使用 练习 2.62 的 union-set
计算两个列表的并集;以上两个程序的复杂度都是 \(\Theta(n)\) 。list->tree
程序,将第二步操作所产生的列表转换成一棵平衡树,复杂度为 \(\Theta(n)\) 。intersection-tree
和 union-tree
的整个过程需要使用三个复杂度为 \(\Theta(n)\) 的程序,但总的复杂度还是 \(\Theta(n)\) ,因此符合题目的要求。
定义:
;;; 65-intersection-tree.scm
(load "63-tree-list-2.scm")
(load "64-list-tree.scm")
(load "p105-intersection-set.scm")
(define (intersection-tree tree another)
(list->tree
(intersection-set (tree->list-2 tree)
(tree->list-2 another))))
测试:
1 ]=> (load "65-intersection-tree.scm")
;Loading "65-intersection-tree.scm"...
; Loading "63-tree-list-2.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "64-list-tree.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "p105-intersection-set.scm"... done
;... done
;Value: intersection-tree
1 ]=> (define it (intersection-tree (list->tree '(1 2 3 4 5))
(list->tree '(1 3 5 7 9))))
;Value: it
1 ]=> it
;Value 11: (3 (1 () ()) (5 () ()))
1 ]=> (tree->list-2 it)
;Value 12: (1 3 5)
定义:
;;; 65-union-tree.scm
(load "62-union-set.scm")
(load "63-tree-list-2.scm")
(load "64-list-tree.scm")
(define (union-tree tree another)
(list->tree
(union-set (tree->list-2 tree)
(tree->list-2 another))))
测试:
1 ]=> (load "65-union-tree.scm")
;Loading "65-union-tree.scm"...
; Loading "62-union-set.scm"... done
; Loading "63-tree-list-2.scm"...
; Loading "p106-tree.scm"... done
; ... done
; Loading "64-list-tree.scm"...
; Loading "p106-tree.scm"... done
; ... done
;... done
;Value: union-tree
1 ]=> (define ut (union-tree (list->tree '(1 2 3 4 5))
(list->tree '(1 3 5 7 9))))
;Value: ut
1 ]=> Ut
;Value 12: (4 (2 (1 () ()) (3 () ())) (7 (5 () ()) (9 () ())))
1 ]=> (tree->list-2 ut)
;Value 13: (1 2 3 4 5 7 9)