Comment créer un arbre de recherche binaire dans Clojure?
-
05-07-2019 - |
Question
Dans Scheme, je peux utiliser define-struct
pour créer un arbre de recherche binaire, mais comment le faire-on dans Clojure?
La solution
Vous pouvez utiliser structmaps. Pour en définir un:
(defstruct bintree :left :right :key)
Pour créer une instance:
(struct-map bintree :left nil :right nil :key 0)
Vous pouvez ensuite accéder aux valeurs de la structure comme suit:
(:left tree)
etc.
Vous pouvez également créer de nouvelles fonctions d'accès:
(def left-branch (accessor bintree :left))
et l'utiliser:
(left-branch tree)
Autres conseils
Je ne connais pas Clojure, mais je parie que c’est la même chose que dans Scheme sans define-struct
... mais contre les branches gauche et droite. Pour trouver quelque chose, recurse jusqu'à frapper un atome.
Sérieusement, les structmaps ressemblent à ce que vous voulez. J'ai trouvé cette . Recherchez les structmaps à mi-chemin.
La méthode la plus simple consiste à utiliser l’arborescence déjà définie dans le langage (chaque carte triée est vraiment une arborescence. Si vous avez simplement besoin d’une fonction différente pour comparer les clés, utilisez "trier par carte".
;;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"