Skip to content

Instantly share code, notes, and snippets.

@metamorph
Last active October 1, 2015 06:23
Show Gist options
  • Save metamorph/bdb90be62e9d242eebf3 to your computer and use it in GitHub Desktop.
Save metamorph/bdb90be62e9d242eebf3 to your computer and use it in GitHub Desktop.
Binary Tree in Clojure. Comments on how to improve the code are welcome. It feels like it's somewhat repetitive, and maybe not fully idiomatic Clojure?
(ns test-bench.core)
(defprotocol BinaryTree
(member? [_ e] "Check if e is a member of the BinaryTree")
(insert [_ e] "Insert an element in the tree")
(delete [_ e] "Remove element from tree"))
;; Need to forward declare factory functions.
(declare leaf node delete)
;; A leaf is an empty node in the tree.
(defn leaf [] (->Leaf))
(defrecord Leaf []
BinaryTree
(member? [this e] false)
(insert [this e] (node e))
(delete [this e] this))
;; A node have an active value and a left/right node.
(defn node
([v] (node v (leaf) (leaf)))
([v l r] (->Node v l r)))
(defrecord Node [value left right]
BinaryTree
(member? [this e]
(if (= value e) true
(if (> e value)
(member? right e)
(member? left e))))
(insert [this e]
(if (= value e) this
(if (> e value)
(node value left (insert right e))
(node value (insert left e) right))))
(delete [this e]
(if (= e value) (removed value left right)
(if (> e value)
(node value left (delete right e))
(node value (delete left e) right)))))
;; A removed node is a place-holder for a removed element.
(defn removed [e l r] (->RemovedNode e l r))
(defrecord RemovedNode [value left right]
BinaryTree
(member? [this e]
(if (= e value) false
(if (> e value)
(member? right e)
(member? left e))))
(insert [this e]
(if (= e value) (node value left right)
(if (> e value)
(delete value left (insert right e))
(delete value (insert left e) right))))
(delete [this e]
(if (= e value) this
(if (> e value)
(node value left (delete right e))
(node value (delete left e) right)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment