SICPを読む(73) 問題2.63 二進木としての集合

Scheme

二進木に入ります。二進木初体験なので、ちゃんと読みたい。

二進木

Schemeで二進木を表すと、

(データ 左 右)

リストは構造体にも化ける。便利だ。

見にくければ、(左 データ 右)と書いても動くと思う。


リストを追加するのが面倒なので、entry-appendr作った。

(define (tree-appendr l)
  (fold
    (lambda (a b)
      (adjoin-set a b))
    '() l))

(entry-appendr '(1 2 3 4 5 6)) ; (1 () (2 () (3 () (4 () (5 () (6 () ()))))))
(entry-appendr '(6 5 4 3 2 1)) ; (6 (5 (4 (3 (2 (1 () ()) ()) ()) ()) ()) ())
(entry-appendr '(4 2 3 1 5 6)) ; (4 (2 (1 () ()) (3 () ())) (5 () (6 () ())))

いちいちadjoin-setしなくてもいい。ステキ。

entryの突っ込み方を間違えると、不釣り合いな木ができてしまう事がよくわった。

不釣り合いな木場合は、順序づけられたリストのと同じステップ数がかかってしまうし、メモリも大量に食う。激しく意味が無いので真ん中から挿入したい。

重要なのは、リストが構造化されただけで、実装は順序づけられたリストと殆んど変わらないってところ。これだけで、検索にかかるステップ数がnからlog nに変わるなんてステッキ。

問題 2.63

tree->listな問題。つまりツリーのフラット化に関すること。

あんまり変わらない。というのが答えかな。

  • aの方はappendと、再帰を使ってるので、オーバーヘッドがある。appendが重め。
  • bは反復なので、軽め。

どっちにしろ、全てのリストを舐める必要があるので、ステップ数はデータの量に比例する。

反復で書いた方が早いけど、気にする程でもない(Schemer的発想)


次の問題はヘビーっぽいので、とりあえずここまで〜。

追記

ツリーの反復が苦手なので、練習した。

二分木 - Wikipediaの、行きがけ順、通りがけ順、帰りがけ順探索について。

; SICPの反復版
(define (tree->list tree)
  (letrec ((copy-to-list
             (lambda (tree result)
               (if (null? tree)
                   result
                   (copy-to-list (left-branch tree)
                                 (cons (entry tree)
                                       (copy-to-list (right-branch tree) result)))))))
    (copy-to-list tree '())))

(tree->list data) ; (1 2 3 4 5 6 7)


; leftとrightを変えると大きい順
(define (tree->list-reverse tree)
  (letrec ((copy-to-list
             (lambda (tree result)
               (if (null? tree)
                   result
                   (copy-to-list (right-branch tree)
                                 (cons (entry tree)
                                       (copy-to-list (left-branch tree) result)))))))
    (copy-to-list tree '())))

(tree->list-reverse data) ; (7 6 5 4 3 2 1)


; consの位置を変更すると、巡った履歴。(逆順)
(define (tree->list-reverse-history tree)
  (letrec ((copy-to-list
             (lambda (tree result)
               (if (null? tree)
                   result
                   (copy-to-list (right-branch tree)
                                 (copy-to-list (left-branch tree)
                                               (cons (entry tree) result)))))))
    (copy-to-list tree '())))

(tree->list-reverse-history data) ; (7 5 6 3 1 2 4)


; 履歴の正順
(define (tree->list-hiltory tree)
  (letrec ((copy-to-list
             (lambda (tree result)
               (if (null? tree)
                   result
                   (cons (entry tree)
                         (copy-to-list (left-branch tree)
                                       (copy-to-list (right-branch tree) result)))))))
    (copy-to-list tree '())))

(tree->list-hiltory data) ; (4 2 1 3 6 5 7)


重要なのはconsの位置。left,rightを変えると大きい方を先に見るか小さい方を先に見るか変えられる。


ツリーの反復は練習あるのみだな・・・。