tags:

views:

379

answers:

3

In Scheme, I can use define-struct to make a binary search tree, but how do you do it in Clojure?

+1  A: 

I don't know Clojure, but I bet it's the same way you do it in Scheme without define-struct ... just cons together the left and right branches. To find something, recurse until you hit an atom.

Seriously, though, structmaps sound like what you want. I found this page. Look for structmaps about half way down.

Nathan Sanders
+4  A: 

You can use structmaps. To define one:

(defstruct bintree :left :right :key)

To make an instance:

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

You can then access the values in the struct like this:

(:left tree)

etc.

Or you can create new accessor functions:

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

and use it:

(left-branch tree)
Eric Normand
+1  A: 

The simplest way would be to use the tree that is already defined in language (every sorted-map is a tree really, if you just need different function to compare keys, 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"
ajuc
Not sorted-set? I think that would be a better fit, and the key could be part of the structs you store. sorted-map forces you to separate out the key and handle it separately forever.
Carl Smotricz
+1 anyway, it's close to what I would have said, had I seen the question back when it was asked.
Carl Smotricz