1 (define (test-case actual expected)
2   (newline)
3   (display "Actual:   ")
4   (display actual)
5   (newline)
6   (display "Expected: ")
7   (display expected)
8   (newline))
9 
10 (define (make-leaf symbol weight)
11   (list 'leaf symbol weight))
12 (define (leaf? object)
13   (eq? (car object) 'leaf))
14 (define (symbol-leaf x) (cadr x))
15 (define (weight-leaf x) (caddr x))
16 
17 (define (make-code-tree left right)
18   (list left
19 	right
20 	(append (symbols left) (symbols right))
21 	(+ (weight left) (weight right))))
22 
23 (define (left-branch tree) (car tree))
24 (define (right-branch tree) (cadr tree))
25 (define (symbols tree)
26   (if (leaf? tree)
27       (list (symbol-leaf tree))
28       (caddr tree)))
29 (define (weight tree)
30   (if (leaf? tree)
31       (weight-leaf tree)
32       (cadddr tree)))
33 
34 (define (decode bits tree)
35   (define (decode-1 bits current-branch)
36     (if (null? bits)
37 	'()
38 	(let ((next-branch
39 	       (choose-branch (car bits) current-branch)))
40 	  (if (leaf? next-branch)
41 	      (cons (symbol-leaf next-branch)
42 		    (decode-1 (cdr bits) tree))
43 	      (decode-1 (cdr bits) next-branch)))))
44   (decode-1 bits tree))
45 (define (choose-branch bit branch)
46   (cond ((= bit 0) (left-branch branch))
47 	((= bit 1) (right-branch branch))
48 	(else (error "bad bit -- CHOOSE-BRANCH" bit))))
49 
50 (define (adjoin-set x set)
51   (cond ((null? set) (list x))
52 	((< (weight x) (weight (car set))) (cons x set))
53 	(else (cons (car set)
54 		    (adjoin-set x (cdr set))))))
55 (define (make-leaf-set pairs)
56   (if (null? pairs)
57       '()
58       (let ((pair (car pairs)))
59 	(adjoin-set (make-leaf (car pair)
60 			       (cadr pair))
61 		    (make-leaf-set (cdr pairs))))))
62 
63 (define (encode message tree)
64   (if (null? message)
65       '()
66       (append (encode-symbol (car message) tree)
67 	      (encode (cdr message) tree))))
68 
69 (define (element-of-set x set)
70   (and (not (null? set))
71        (or (equal? x (car set))
72 	   (element-of-set x (cdr set)))))
73 
74 (define (encode-symbol sym tree)
75   (cond ((null? tree) (error "empty tree"))
76 	((not (element-of-set sym (symbols tree))) 
77 	 (error "symbol not in tree"))
78 	((leaf? tree) '())
79 	((element-of-set sym (symbols (left-branch tree))) 
80 	 (cons 0 (encode-symbol sym (left-branch tree))))
81 	((element-of-set sym (symbols (right-branch tree)))
82 	 (cons 1 (encode-symbol sym (right-branch tree))))))
83 
84 (define (generate-huffman-tree pairs)
85   (successive-merge (make-leaf-set pairs)))
86 
87 (define (successive-merge leaf-set)
88   (cond ((null? leaf-set) (error "no leaves in leaf-set"))
89 	((null? (cdr leaf-set)) (car leaf-set))
90 	(else (successive-merge (adjoin-set (make-code-tree (cadr leaf-set) 
91 							    (car leaf-set))
92 					    (cddr leaf-set))))))
93 
94 ;; Exercise 2.71.  Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^n-1. Sketch the tree for n=5; for n=10. In such a tree (for general n) how many bits are required to encode the most frequent symbol? the least frequent symbol? 
95 
96 ;; for a tree of n symbols, 1 bit for most frequent; n-1 bits for least frequent symbol
97 
98 ;; Exercise 2.72.  Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet. 
99 
100 (define (encode message tree)
101   (if (null? message)
102       '()
103       (append (encode-symbol (car message) tree)
104 	      (encode (cdr message) tree))))
105 
106 (define (element-of-set x set)
107   (and (not (null? set))
108        (or (equal? x (car set))
109 	   (element-of-set x (cdr set)))))
110 
111 (define (encode-symbol sym tree)
112   (cond ((null? tree) (error "empty tree"))
113 ;;      we're going to pretend this isn't here to speed up the procedure
114 ;;	((not (element-of-set sym (symbols tree))) 
115 ;;	 (error "symbol not in tree"))
116 	((leaf? tree) '())
117 	((element-of-set sym (symbols (left-branch tree))) 
118 	 (cons 0 (encode-symbol sym (left-branch tree))))
119 	((element-of-set sym (symbols (right-branch tree)))
120 	 (cons 1 (encode-symbol sym (right-branch tree))))))
121 
122 we must call encode-symbol the same number of times as the length of message
123 So, if message is m elements long, we must call encode-symbol m times
124 
125 Within encode-symbol, we must check through the list of symbols either on the left-branch or on the right-branch. If the symbol is on the left-branch, we just check 1 element. Otherwise, we must check, on average, (n-1)/2 elements. There is roughly a 50-50 chance that the symbol will be on the left-branch vs. right-branch.
126 
127 50%: 1
128 25%: (n-1)/2 + 1
129 12.5%: (n-1)/2 + (n-2)/2 + 1
130 6.25%: ...
131 
132 Most frequent symbols O(1), but least-frequent symbol is O(n^2)