Comment créer un arbre de recherche binaire dans Clojure?

Question

Dans Scheme, je peux utiliser define-struct pour faire un arbre de recherche binaire, mais comment le faites-vous dans Clojure?

Answer 1

Vous pouvez utiliser des structmaps. Pour définir un:

(defstruct bintree :left :right :key) 

Pour faire une instance:

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

Vous pouvez alors accéder aux valeurs de la struct comme ceci:

(:left tree) 

etc.

Ou vous peut créer de nouvelles fonctions d'accesseur:

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

et de l'utiliser:

(left-branch tree) 

Answer 2

Je ne connais pas Clojure, mais je parie que c'est comme ça que vous le faites dans Scheme sans define-struct ... juste contre les branches gauche et droite. Pour trouver quelque chose, recurse jusqu'à ce que vous frappiez un atome.

Sérieusement, cependant, structmaps ressemble à ce que vous voulez. J'ai trouvé this page. Recherchez les structmaps à mi-chemin.

Answer 3

La façon la plus simple serait d'utiliser l'arbre qui est déjà défini dans la langue (chaque-carte triée est un arbre vraiment, si vous avez juste besoin d'une fonction différente pour comparer les clés, utilisez trié-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"