Clojureでどのようにバイナリ検索ツリーを作成しますか？

Question

Schemeでは、define-structを使用してバイナリ検索ツリーを作ることができますが、Clojureではどうしますか？

Answer 1

structmapsを使用できます。 1を定義するには：

(defstruct bintree :left :right :key) 

インスタンスを作成するには：

(struct-map bintree :left nil :right nil :key 0) 

あなたは、このような構造体の値にアクセスすることができます

(:left tree) 

など

それとも、新しいアクセサ関数を作成できます：

(def left-branch (accessor bintree :left)) 

し、それを使用します。

(left-branch tree) 

Answer 2

Clojureは分かりませんが、私はSchemeでこれをやっているのと同じ方法だと思います。define-struct ...左右の枝を一緒に共謀させないでください。何かを見つけるには、原子を打つまで繰り返す。

真剣には、あなたが望むようにstructmapsが鳴ります。私はthis pageを見つけました。半分ほど下にあるstructmapsを探してください。

Answer 3

あなただけのキーを比較するためにさまざまな機能が必要な場合は、すべてのソートマップが本当に木である（言語ですでに定義されている木を使用することです最も簡単な方法は、 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"