Clojureでバイナリ検索ツリーを作成するにはどうすればよいですか?
-
05-07-2019 - |
質問
Schemeでは、 define-struct
を使用してバイナリ検索ツリーを作成できますが、Clojureではどのように行うのですか?
解決
構造マップを使用できます。定義するには:
(defstruct bintree :left :right :key)
インスタンスを作成するには:
(struct-map bintree :left nil :right nil :key 0)
その後、次のように構造体の値にアクセスできます。
(:left tree)
etc。
または、新しいアクセサー関数を作成できます:
(def left-branch (accessor bintree :left))
それを使用します:
(left-branch tree)
他のヒント
Clojureについては知りませんが、 define-struct
なしでSchemeで行うのと同じ方法だと思います...左右のブランチをまとめます。何かを見つけるには、アトムに到達するまで再帰します。
しかし、真剣に、structmapsはあなたが望むもののように聞こえます。 このページを見つけました。半分ほど下の構造マップを探します。
最も簡単な方法は、すでに言語で定義されているツリーを使用することです(ソートされたマップはすべてツリーです。キーを比較するために異なる関数が必要な場合は、sorted-map-byを使用します)。
;;define function for comparing keys
(defn compare-key-fn [key1 key2] (< key1 key2) )
;;define tree and add elements
(def my-tree
(-> ;;syntax sugar
(sorted-map-by compare-key-fn) ;;this returns empty tree with given function to compare keys
(assoc 100 "data for key = 100") ;;below we add elements to tree
(assoc 2 "data for key = 2")
(assoc 10 "data for key = 10")
(assoc -2 "data for key = -1")))
;;accesing elements by key
(prn "element for key 100 =" (my-tree 100))
;;"erasing" elements from tree - in reality, what we are really doing, is returning a new tree that contains all elements of the old one, except the element we've just erased.
(def my-new-tree
(dissoc my-tree 2))
(prn my-new-tree) ;; to verify, that element 2 is "erased"
所属していません StackOverflow