¿Cómo se hace un árbol de búsqueda binario en Clojure?

Question

En Scheme, puedo usar define-struct para hacer un árbol de búsqueda binaria, pero ¿cómo lo haces en Clojure?

Answer 1

Puede usar structmaps. Para definir una:

(defstruct bintree :left :right :key) 

Haciendo ejemplo:

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

luego podrás acceder a los valores de la estructura como esta:

(:left tree) 

etc.

O puede crear nuevas funciones de acceso:

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

y utilizarla:

(left-branch tree) 

Answer 2

No sé Clojure, pero apuesto a que es la misma forma en que lo haces en Scheme sin define-struct ... solo contra las ramas izquierda y derecha. Para encontrar algo, recurse hasta que golpee un átomo.

En serio, structmaps suena como lo que quieres. Encontré this page. Busque structmaps a mitad de camino.

Answer 3

La forma más sencilla sería utilizar el árbol que ya está definido en el lenguaje (cada-mapa Ordenado es un árbol de verdad, si sólo tiene funciones diferentes para comparar claves, use 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"