Wie stellen Sie einen binären Suchbaum in Clojure?

Question

In Schema, ich kann define-struct verwenden, um einen binären Suchbaum zu machen, aber wie wollen Sie tun es in Clojure?

Answer 1

Sie können structmaps verwenden. So definieren Sie ein:

(defstruct bintree :left :right :key)

Um eine Instanz zu machen:

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

Sie können dann die Werte zugreifen in der Struktur wie folgt aus:

(:left tree)

etc.

Sie können auch neue Zugriffsfunktionen erstellen:

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

und verwenden es:

(left-branch tree)

Answer 2

Ich weiß nicht, Clojure, aber ich wette, es ist das gleiche, wie Sie es in Schema tun, ohne define-struct ... nur cons zusammen, um die linken und rechten Zweige. Für etwas, recurse, bis Sie ein Atom treffen.

Im Ernst, aber structmaps Sound wie das, was Sie wollen. Ich fand dieser Seite . Suchen Sie nach structmaps etwa auf halbem Weg nach unten.

Answer 3

Der einfachste Weg wäre, um den Baum zu verwenden, die bereits in der Sprache definiert ist (jede sortiert-Karte ist ein Baum wirklich, wenn Sie nur andere Funktion müssen vergleichen Tasten, Verwendung sortierte-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"