Как создать бинарное дерево поиска в Clojure?
-
05-07-2019 - |
Вопрос
В Схеме я могу использовать define-struct
создать бинарное дерево поиска, но как вы это делаете в Clojure?
Решение
Вы можете использовать structmaps .Чтобы определить один:
(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)
Другие советы
Я не знаю Clojure, но держу пари, что точно так же, как вы делаете это в Схеме без define-struct
... просто объединяет левую и правую ветви. Чтобы найти что-то, повторяйте, пока не дойдете до атома.
Серьезно, структурные карты звучат так, как вы хотите. Я нашел эту страницу . Ищите структурные карты примерно на полпути вниз.
Простейшим способом было бы использовать дерево, которое уже определено в языке (каждая отсортированная карта действительно является деревом; если вам просто нужна другая функция для сравнения ключей, используйте 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"