Come si crea un albero di ricerca binario in Clojure?

Question

In Scheme, posso usare define-struct per creare un albero di ricerca binario, ma come si fa in Clojure?

Answer 1

È possibile utilizzare structmaps. Per definire uno:

(defstruct bintree :left :right :key) 

Per effettuare un'istanza:

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

È quindi possibile accedere ai valori nella struct come questo:

(:left tree) 

ecc

Oppure si può creare nuove funzioni di accesso:

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

e usarlo:

(left-branch tree) 

Answer 2

Non conosco Clojure, ma scommetto che è lo stesso modo in cui lo si fa in Scheme senza define-struct ... basta tenere insieme i rami sinistro e destro. Per trovare qualcosa, recita finché non colpisci un atomo.

Seriamente, però, le structmap suonano come quello che vuoi. Ho trovato this page. Cerca structmaps a metà strada.

Answer 3

Il modo più semplice sarebbe quella di utilizzare l'albero che è già definito nel linguaggio (ogni ordinato-map è un albero davvero, se avete solo bisogno funzione diversa per confrontare le chiavi, usa la mappa ordinata).

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