blob: ca26639f69a6955fa5ba059d732fcfb965c5875b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#lang racket
(require "../../shared/sets.rkt")
;; 2*O(n) + O(n) + O(n)
(define (union-set s1 s2)
(define (ordered-list-union-set set1 set2)
(cond
((and (null? set1) (null? set2)) '())
((null? set1) (cons (car set2) (ordered-list-union-set set1 (cdr set2))))
((null? set2) (cons (car set1) (ordered-list-union-set (cdr set1) set2)))
((= (car set1) (car set2)) (cons (car set2) (ordered-list-union-set (cdr set1) (cdr set2))))
((> (car set1) (car set2)) (cons (car set2) (ordered-list-union-set set1 (cdr set2))))
((< (car set1) (car set2)) (cons (car set1) (ordered-list-union-set (cdr set1) set2)))))
(list->tree
(ordered-list-union-set (tree->list s1) (tree->list s2))))
;; 2*O(n) + O(n) + O(n)
(define (intersection-set set1 set2)
(define (ordered-list-intersection-set s1 s2)
(if (or (null? s1) (null? s2))
'()
(let ((x1 (car s1)) (x2 (car s2)))
(cond ((= x1 x2)
(cons x1
(ordered-list-intersection-set
(cdr s1)
(cdr s2))))
((< x1 x2)
(ordered-list-intersection-set
(cdr s1)
s2))
((> x1 x2)
(ordered-list-intersection-set
s1
(cdr s2)))))))
(list->tree
(ordered-list-intersection-set
(tree->list set1) (tree->list set2))))
((lambda ()
(println "tree -- UNION")
(define test216a (make-entry
7
'()
'()))
(define test216b (make-entry
4
(make-entry 1 '() '())
(make-entry
8
(make-entry 6 '() '())
(make-entry
10
'()
(make-entry
12
'()
'())))))
(println (union-set
(list->tree (tree->list test216a))
(list->tree (tree->list test216b))))
(println (intersection-set
(list->tree (tree->list test216a))
(list->tree (tree->list test216b))))
(newline)))
|
