Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-05-03

ArcでL-99 (P57 二分探索木の作成)

| 10:51 | ArcでL-99 (P57 二分探索木の作成) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P57 二分探索木の作成) - わだばLisperになる

久々のArc。今回のお題は、数値のリストを二分探索木的に配置しましょう、というもの。

また、その結果を前回作成した、symmetric?で確認してみよう、とのことです。

(construct '(3 2 5 7 1))
;=> (3 (2 (1 nil nil) nil) (5 nil (7 nil nil)))

;; symmetric?で確認
(symmetric? (construct '(5 3 18 1 4 12 21)))
;=> t

(symmetric? (construct '(3 2 5 7 1)))
;=> nil

(def add-leaf (leaf tree)
  (with ((root left right) tree
         node `(,leaf () () ))
    (if (<= leaf root)
        (if no.left
            `(,root ,node ,right)
            `(,root ,(add-leaf leaf left) ,right))
        (if no.right
            `(,root ,left ,node)
            `(,root ,left ,(add-leaf leaf right))))))

(def construct (lst)
  (reduce (fn (lst leaf) (add-leaf leaf lst))
          (let (head . tail) lst
            (cons `(,head () () ) tail))))