(sicp24)m2.63

;; 今度はリストではなく2進木のデータ構造
;; 今までのデータ構造
;; 並び→並び（重複あり）→並び（sort済み）→2進木

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

(let* ((target (make-tree 5 '(1) '(10)))
      (f (lambda (f) (null-print (f target)))))
  (f entry)
  (f left-branch)
  (f right-branch))

;; gosh> 5
;; (1)
;; (10)
;;この様なmake-treeの使い方は間違い。
      
  

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

(let* ((no-leaf (lambda (x) (make-tree x '() '())))
       (target (make-tree 5 (no-leaf 1) (no-leaf 10))))
  (null-print (filter (lambda (x) (element-of-set? x target))
          (enumerate-interval 1 5)))
  (null-print (adjoin-set 3 (adjoin-set 7 target))))

;; gosh> (1 5)
;; (5 (1 () (3 () ())) (10 (7 () ()) ()))

;;m2.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)))))
  (copy-to-list tree '()))

;a
;; tree->list-1とtree->list-2の2つの手続きは同じ結果を生じると思う。
;; たぶん同じ処理をtree->list-1は再帰的に、tree->list-1は反復的に作っている。
;; そしてこれらの処理が返すのは、要素が昇順に並んでいるリスト。

(let* ((a adjoin-set)
       (no-leaf (lambda (x) (make-tree x '() '())))
       (a-list (a 11 (a 5 (a 1 (a 3 (a 9 (no-leaf 7)))))))
       (b-list (a 11 (a 9 (a 5 (a 7 (a 1 (no-leaf 3)))))))
       (c-list (a 11 (a 7 (a 1 (a 9 (a 3 (no-leaf 5)))))))
       (p (lambda (f)
            (null-print "a: " (f a-list))
            (null-print "b: " (f b-list))
            (null-print "c: " (f c-list)))))
  (p tree->list-1)
  (p tree->list-2))

;; gosh> a: (1 3 5 7 9 11)
;; b: (1 3 5 7 9 11)
;; c: (1 3 5 7 9 11)
;; a: (1 3 5 7 9 11)
;; b: (1 3 5 7 9 11)
;; c: (1 3 5 7 9 11)

;;b
;;遅いのは再帰的に手続きされているtree->list-1の方。
;; 手間の違いはtree->list-1がO(n log n)でtree->list-2がO(n)
;; 具体的には、
;; appendが木の深さ分適用されるのでlog(n)の手間
;; tree->list-1が適用されるのはO(n)
;; (2*要素数回の様な気もする）