SICP 読書ノート#17 - 2.3.4 Huffman符号化木(1) (pp.94-99)

おおよそ理解できてるつもりだけど、問題 2.69が上手く解けない。

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge leafs)
  (if (null? leafs)
      nil
      (successive-merge-1 (cdr leafs) (car leafs))))

(define (successive-merge-1 leafs tree)
  (if (null? leafs)
      tree
      (successive-merge-1 (cdr leafs)
                          (make-code-tree (car leafs) tree))))

確認。

racket@> (equal? (generate-huffman-tree (list '(A 4) '(B 2) '(D 1) '(C 1)))
                 sample-tree)
#t

動いてる。

ただしこれだと右に偏った木になってしまう。

racket@> (generate-huffman-tree (list '(A 8) '(B 3) '(C 1) '(D 1) '(E 1) '(F 1) '(G 1) '(H 1)))

'((leaf A 8)
  ((leaf B 3)
   ((leaf C 1)
    ((leaf D 1)
     ((leaf E 1)
      ((leaf F 1) ((leaf G 1) (leaf H 1) (G H) 2) (F G H) 3)
      (E F G H)
      4)
     (D E F G H)
     5)
    (C D E F G H)
    6)
   (B C D E F G H)
   9)
  (A B C D E F G H)
  17)

図2.18(p95)のように、ある程度左右のバランスが獲れるようにするにはどうすればいいんだろう？

---

※「SICP読書ノート」の目次はこちら