Como você faz uma árvore de busca binária em Clojure?

Question

No esquema, posso usar define-struct para fazer uma árvore de busca binária, mas como você fazê-lo em Clojure?

Answer 1

Você pode usar structmaps. Para definir um:

(defstruct bintree :left :right :key)

Para fazer uma instância:

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

Você pode acessar os valores na estrutura como esta:

(:left tree)

etc.

Ou você pode criar novas funções de acesso:

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

e usá-lo:

(left-branch tree)

Answer 2

Eu não sei Clojure, mas eu aposto que é a mesma maneira que você faz no Esquema sem define-struct ... apenas contras juntos os ramos direito e esquerdo. Para encontrar alguma coisa, recurse até atingir um átomo.

A sério, porém, structmaps soar como o que você quer. Eu encontrei desta página . Procure structmaps cerca de metade do caminho para baixo.

Answer 3

A maneira mais simples seria usar a árvore que já está definido no idioma (todos os-map ordenados é uma árvore muito, se você só precisa função diferente para comparar as chaves, o uso ordenado-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"