Deleting any node inside BST - Clojure

Question

I'm studying algorithms and at the class we were asked to create a BST with structures, I'm trying really hard to create a delete function but the one I created isn't efficient and doesn't work. I searched in google for something similar, but most of the questions are about vectors and not record/structures. If you have any recommendations, I would really appreciate it.

This is the basic creating of the root and node:

(let [bst (make-bst)]
  (bst-empty? bst)
  (make-bst-node 10))

(defrecord BST [root])

(defn bst? [bst]
  (= (class bst) BST))

(defn make-bst []
  (BST. (ref nil)))

(defn bst-empty? [bst]
  (nil? @(:root bst)))

(defrecord BSTnode [data left right])

(defn make-bst-node [val]
  (BSTnode. val (ref nil) (ref nil)))

(defn bst-insert! [bst val]
  (loop [node (:root bst)]
    (if (nil? @node)
      (dosync
       (ref-set node (make-bst-node val)))
      (let [data (:data bst)]
        (if (< val data)
          (recur (:left @node))
          (if (val data)
            (recur (:right @node))))))))

This is the delete function:

(defn bst-del [bst val]
  (if (nil? @(:root bst))
    false
    (do
    (if (= (:data @(:root bst)) val)
     (if (nil? (and (:right bst) (:left bst)))
      (dosync
       (ref-set (:root bst) nil))
       (if (not (nil? (:right bst)))
         (dosync
          (ref-set (:root bst) @(:right bst)))
         (if (not (nil? (:left bst)))
           (dosync
            (ref-set (:root bst) @(:left bst)))
           (if (not (nil? (and (:right bst) (:left bst))))
             (dosync
              (ref-set (:root bst) @(:left bst))
              (ref-set (:root bst) (:right bst))) false))))))))

(defn node-del [bst val]
  (loop [node @(:root bst)]
    (if (nil? node)
      false
      (if (true? bst-del)
        (println "somthing got deleted")
        (if (< val (:data node))
          (recur @(:left node))
          (recur @(:right node)))))))

I tried to search in google but all the function or examples were for maps and vectors, not my case, as well as, reading theoretical material about the subject and references from different languages.

Answer 1

this code of yours seems to be overly complicated and hard to debug (or event understand an algorithm)

I would propose implementing this recursive algorithm for deletion, which works quite nice with that mutable structure of yours:

Node delete(root : Node, z : T):               
  if root == null
    return root
  if z < root.key
    root.left = delete(root.left, z)
  else if z > root.key
    root.right = delete(root.right, z)
  else if root.left != null and root.right != null
    root.key = minimum(root.right).key
    root.right = delete(root.right, root.key)
  else
    if root.left != null
      root = root.left
    else if root.right != null
      root = root.right
    else
      root = null
  return root

so, i would start with the following type defs:

(defrecord Tree [root])

(defn make-tree [root-node]
  (->Tree (ref root-node)))

(defrecord Node [data left right])

(defn make-node [data & {:keys [left right]}]
  (->Node (ref data)
          (ref left)
          (ref right)))

first thing we want is insertion + traversal functions for tree creating/debug. let's implement them for Node (and employ in Tree later):

(defn insert-node [{:keys [data left right] :as node} item]
  (if (nil? node)
    (make-node item)
    (dosync (alter (if (< item @data) left right)
                   insert-node
                   item)
            node)))

(defn traverse-node [node]
  (when-some [{:keys [data left right]} node]
    (concat (traverse-node @left)
            [@data]
            (traverse-node @right))))

user> (reduce insert-node nil [3 1 2])
;; {:data #<Ref@1a28bd3f: 3>,
;;  :left
;;  #<Ref@514133ef: 
;;    {:data #<Ref@5617f393: 1>,
;;     :left #<Ref@637de49b: nil>,
;;     :right
;;     #<Ref@6efa5317: 
;;       {:data #<Ref@14ef556b: 2>,
;;        :left #<Ref@7fe0e031: nil>,
;;        :right #<Ref@5a16bba5: nil>}>}>,
;;  :right #<Ref@4eec6b9f: nil>}

user> (traverse-node (reduce insert-node nil [3 1 2]))
;; (1 2 3)

so, this seems to work ok.

Next, we will implement the deletion algorithm. there's an utility function minimum in the aforementioned algorithm, so we start with that one:

(defn minimum-node [{:keys [data left right] :as node}]        
  (cond (nil? node) nil
        (nil? @left) @data              
        :else (recur @left)))

user> (minimum-node (reduce insert-node nil (shuffle (range 10 20))))
;; 10

after that the deletion implementation looks trivial:

(defn del-node [node item]
  (when-some [{:keys [data left right]} node]
    (cond (< item @data) (dosync (alter left del-node item)
                                 node)
          (> item @data) (dosync (alter right del-node item)
                                 node)
          (and (some? @left) (some? @right)) (let [m (-> right deref minimum-node)]
                                               (dosync 
                                                (ref-set data m)
                                                (alter right del-node m))
                                               node)
          (some? @left) @left
          (some? @right) @right)))


user> (traverse-node (del-node
                      (reduce insert-node nil (shuffle (range 10 20)))
                      13))
;;=> (10 11 12 14 15 16 17 18 19)

this seems to be working mutable algorithm.

Let's then go back to the Tree structure. I would start with the BST protocol, to be used by both Node and Tree:

(defprotocol BST
  (traverse [self])
  (insert [self item])
  (minimum [self])
  (del [self item]))

(extend-protocol BST
  Node
  (traverse [self]
    (traverse-node self))
  (insert [self item]
    (insert-node self item))
  (minimum [self]
    (minimum-node self))
  (del [self item]
    (del-node self item)))

(extend-protocol BST
  Tree
  (traverse [self] (-> self :root deref traverse))
  (insert [self item]
    (dosync
     (if (-> self :root deref some?)     
       (alter (:root self) insert item)
       (ref-set (:root self) (make-node item))))
    self)
  (minimum [self] (-> self :root deref minimum))
  (del [self item]
    (dosync
     (when (-> self :root deref some?)      
       (alter (:root self) del item)))
    self))

and that's it. Now just use it:

user> (reduce del
              (reduce insert (make-tree nil) [1 2 3 4])
              [2 4])
;; {:root
;;  #<Ref@273f7854: 
;;    {:data #<Ref@67d4f4d0: 1>,
;;     :left #<Ref@26329ec3: nil>,
;;     :right
;;     #<Ref@5636f9f8: 
;;       {:data #<Ref@3cd02119: 3>,
;;        :left #<Ref@7d62fb13: nil>,
;;        :right #<Ref@1f25eeb7: nil>}>}>}

Answer 2

After the class, I understood how to delete a function and I implemented it similarly inside a dictionary binary tree. It is really similar, the only difference is with "key" value, but the logic is the same.

(defn dict-find-leftmost-node[start-node]
  (loop [node start-node]
    (if (nil? @(:left @node))
      node
      (recur (:left @node)))))

(defn dict-remove! [dict key]
  (let [node-to-remove (dict-get-node dict key)]
    (when (not (nil? node-to-remove))
      (if (dict-node-leaf? node-to-remove)
        (dosync
         (ref-set node-to-remove nil))
        (if (nil? @(:left @node-to-remove))
          (dosync
           ;;(println "I need to pull up the right branch")
           (ref-set node-to-remove
                    @(:right @node-to-remove)))
          (if (nil? @(:right @node-to-remove))
            (dosync
             ;;(println "I need to pull up the left branch")
             (ref-set node-to-remove
                      @(:left @node-to-remove)))
            (let [leftmost-node
                  (dict-find-leftmost-node
                   (:right @node-to-remove))]
              (dosync
               (ref-set (:left @leftmost-node)
                        @(:left @node-to-remove))
               (ref-set node-to-remove
                        @(:right @node-to-remove))))
               
              ;;(println "I don't know what to do yet!")
        ;; this is where we remove the node
        ))))))

(defn dict-node-leaf? [node]
  (and (nil? @(:left @node))
       (nil? @(:right @node))))