Jak zrobić drzewo wyszukiwania binarnego w Clojure?

Question

W Schemacie mogę użyć drzewa define-struct do utworzenia drzewa wyszukiwania binarnego, ale jak to zrobić w Clojure?

Answer 1

Możesz użyć structmaps. Aby zdefiniować jedno:

(defstruct bintree :left :right :key) 

Aby instancję:

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

Następnie można uzyskać dostęp do wartości w struct tak:

(:left tree) 

itp

Lub może tworzyć nowe funkcje dodatkowe:

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

i używać go:

(left-branch tree) 

Answer 2

Nie znam Clojure, ale założę się, że to tak samo, jak robisz to na Scheme bez define-struct ... po prostu skontrastuje lewą i prawą gałąź. Aby znaleźć coś, powracaj, póki nie trafisz na atom.

Poważnie, jednak mapy strukturalne brzmią jak tego, co chcesz. Znalazłem this page. Poszukaj map struktury w połowie długości.

Answer 3

Najprostszym sposobem byłoby użyć drzewa, który jest już zdefiniowany w języku (co sortowane-map jest drzewem naprawdę, jeśli wystarczy inną funkcję porównać klucze, użyj posortowanej mapy-według).

;;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"