Как Вы делаете дерево двоичного поиска в Clojure?
Никакая книга не будет в состоянии касаться всех возможных сценариев. Это также зависит от того, что Вы, как будут ожидать, сделаете с проектом и существует ли какой-либо вид внешней спецификации.
- , Если необходимо будет только сделать случайные небольшие изменения, просто сделайте их и не потрудитесь начинать осуществлять рефакторинг.
- , Если существует спецификация (или можно заставить кого-то писать это), рассмотрите полную перезапись, если это может быть выровнено по ширине обозримым количеством изменений в проекте
- , Если "реализация является спецификацией" и существует много запланированных изменений, то Вы в значительной степени политы из шланга. Запишите много из модульные тесты и начните осуществлять рефакторинг на маленьких шагах.
На самом деле, модульные тесты будут неоценимыми независимо от того, что Вы делаете (если можно записать им в интерфейс, это не собирается изменяться очень с рефакторингами или перезаписью, которая является).
3 ответа
Вы можете использовать карты структуры. Чтобы определить один:
(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, но держу пари, что это то же самое, что вы делаете в Scheme без 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"