blob: 7b99c77ff48f3a78f3c8859e3f3ccdc2584163a3 (
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#lang racket
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-entry entry left right)
(list entry left right))
(define (element-of-set? x mset)
(cond ((null? mset) false)
((= x (entry mset)) true)
((> x (entry mset))
(element-of-set? (right-branch mset)))
((< x (entry mset))
(element-of-set? (left-branch mset)))))
(define (adjoin-set x mset)
(cond ((null? mset) (make-tree x '() '()))
((= x (entry mset)) mset)
((< x (entry mset))
(make-tree
(entry mset)
(adjoin-set x (left-branch mset))
(right-branch mset)))
((> x (entry))
(make-tree
(entry mset)
(left-branch mset)
(adjoin-set x (right-branch mset))))))
(define (tree->list-1 tree)
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))
;; depth of a balanced tree with n elements is log n.. right? Because every level you need 2*(level-1) elements, so the total levels is how many time we can do that step until 2*levels > n.
;; So it is the log a where a is the smallest number that only has factor 2 and > n.
;; EDIT this is incomplete. Since the recursive call is done multiple times we get a geometric series with base 2 that describes the number of units of work done.
;; It can be shown that this is O(2n) asymptotically by using the identity for powerseries.
;; Both procedure 1 and 2 are reducing the problem the same way using tree recursion.
;; Only the overhead spent at each level is greater for 1, because append is used in the linear recursive process.
;; Since at every level we do a linear scan of all left elements, it is a*n*n on average. Where a is a factor that corrects for the fact that we have to scan halve at each depth.
;; 1 is a linear iterative procedure and has almost no overhead at every level except a cons operation so it is O(n) on average.
((lambda ()
(define test216a (make-entry
7
(make-entry)
9
(make-entry
3
(make-entry
1 '() '())
(make-entry 5 '() '()
(make-entry
11
'()
'())))))
(println (tree->list-1 test216a))
(println (tree->list-2 test216a))
(newline)
(define test216b (make-entry
3
(make-entry 1 '() '())
(make-entry
7
(make-entry 5 '() '())
(make-entry
9
'()
(make-entry
11
'()
'())))))
(println (tree->list-1 test216b))
(println (tree->list-2 test216b))
(newline)
(define test216c (make-entry
5
(make-entry 3 (make-entry 1 '() '()) '())
(make-entry
9
(make-entry 7 '() '())
(make-entry
11
'()
'()))))
(println (tree->list-1 test216c))
(println (tree->list-2 test216c))
(newline)))
|
