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-18

ArcでL-99 (P59 左右で高さのバランスのとれた二分木)

| 05:09 | ArcでL-99 (P59 左右で高さのバランスのとれた二分木) - わだばLisperになる を含むブックマーク はてなブックマーク - ArcでL-99 (P59 左右で高さのバランスのとれた二分木) - わだばLisperになる

ここでいう左右で高さのバランスのとれた二分木とは、左右の木た高さの差が±1までの二分木とのこと。

本来バックトラックで解くところですが、全通り生成しております。

そして、hbal-treeで条件を満した木を選り分けているのですが、最初から条件を満した木を生成してしまっているため、意味のないことになっております…。

;(each x (firstn 5 (hbal-tree 3)) (prn x))
;>>>
;(x (x (x nil nil) (x nil nil)) (x (x nil nil) (x nil nil)))
;(x (x (x nil nil) nil) (x (x nil nil) (x nil nil)))
;(x (x nil (x nil nil)) (x (x nil nil) (x nil nil)))
;(x (x (x nil nil) (x nil nil)) (x (x nil nil) nil))
;(x (x (x nil nil) nil) (x (x nil nil) nil))

(def hbal-tree (h)
  (keep hbal-tree-p gen-tree-h.h))

(def gen-tree-h (h)
  (case h
    0 '(())
    1 '((x () ()))
    (with (h-1 (gen-tree-h (- h 1))
           h-2 (gen-tree-h (- h 2)))
      (map (fn (tree) `(x ,@tree))
           `(,@(comb2 h-1 h-1)
             ,@(comb2 h-1 h-2)
             ,@(comb2 h-2 h-1))))))

(def hbal-tree-p (tree)
  (let (_ left right) tree
    (>= 1 (abs (- tree-height.left 
                  tree-height.right))))

(def tree-height (tree)
  (let (_ left right) tree
    (if tree
        (+ 1 (max tree-height.left
                  tree-height.right))
        0)))