問題2-63〜65

集合の要素を二進木で表現した場合に関する問題です。木の節の要素よりも値が小さければ左側へ、大きければ右側へという規則を設けることによって、木全体が釣り合っていれば、探索処理を対数的に効率化することができます。それらを表すための各手続きは、以下のように本書の中で表現されていました。

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)
  (list entry left right))

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

木を作るのが面倒くさいのですが、以下のように作成して、上記の手続きを利用してみます。

(define tree1
  (make-tree 7 
             (make-tree 3 
                        (make-tree 1 '() '())
                        (make-tree 5 '() '()))
             (make-tree 9 
                        '() 
                        (make-tree 11 '() '()))))

(define tree2
  (make-tree 3
             (make-tree 1 '() '())
             (make-tree 7
                        (make-tree 5 '() '())
                        (make-tree 9
                                   '()
                                   (make-tree 11 '() '())))))

(define tree3
  (make-tree 5
             (make-tree 3
                        (make-tree 1 '() '())
                        '())
             (make-tree 9
                        (make-tree 7 '() '())
                        (make-tree 11 '() '()))))

(element-of-set? 3 tree3)  ;=>#t
(element-of-set? 4 tree3)  ;=>#f
(adjoin-set 8 tree1)  ;=>(7 (3 (1 () ()) (5 () ())) (9 (8 () ()) (11 () ())))

解読しにくいですが、adjoin-setによって、新しい要素も正しい位置に追加されているようです。
そこで、問題2-63ですが、ツリー化されている要素を順序通りに並んだリストに変換するための手続きが例文として掲載されています。

(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)))))

(tree->list-1 tree1)  ;=>(1 3 5 7 9 11)
(tree->list-1 tree2)  ;=>(1 3 5 7 9 11)
(tree->list-1 tree3)  ;=>(1 3 5 7 9 11)

(tree->list-2 tree1)  ;=>(1 3 5 7 9 11)
(tree->list-2 tree2)  ;=>(1 3 5 7 9 11)
(tree->list-2 tree3)  ;=>(1 3 5 7 9 11)

どちらも正しく動いているようです。問題aには結果が異なるかもしれないみたいなことが書かれていますが、そのようなツリーを思いつくことができませんでした。問題bに関しては、tree-list-1の方がappendを使っている分、左側に重心が傾いていたらステップが多くなるのではないでしょうか。appendがp58のような実装だったらの場合ですが、appendを呼び出すたびに、リストを作成しなおす処理が走ってしまいます。

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

次の問題2-64は、任意のリストからバランスのとれたツリーを作成する手続きが掲載されていて、これは是非とも欲しいと思いましたが、そこに書かれている処理の複雑さを理解することはできませんでした。残念です。そのため、問題2-65も手つかずのままです。