删除 BST 内的任何节点 - Clojure

Question

我正在学习算法，在课堂上我们被要求创建一个带有结构的 BST，我非常努力地创建一个删除函数，但我创建的函数效率不高并且不起作用。我在谷歌中搜索了类似的内容，但大多数问题都是关于向量而不是记录/结构。如果您有任何建议，我将非常感激。

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)))))))

我尝试在谷歌中搜索，但所有功能或示例都是针对地图和矢量的，而不是我的情况，以及阅读有关该主题的理论材料和来自不同语言的参考文献。

Answer 1

你的这段代码似乎过于复杂并且难以调试（或者事件理解算法）

我建议实现这个递归删除算法，它与你的可变结构配合得很好：

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

所以，我将从以下类型开始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)))

我们想要的第一件事是用于树创建/调试的插入+遍历函数。让我们为 Node 实现它们（稍后在 Tree 中使用）：

(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)

所以，这似乎工作正常。

接下来我们来实现删除算法。
上述算法中有一个实用函数minimum，因此我们从该函数开始：

(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

之后删除实现看起来微不足道：

(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)

这似乎是工作可变算法。

然后让我们回到Tree 结构。我将从 BST 协议开始，供 Node 和 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))

就是这样。现在只需使用它：

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

课后，我了解了如何删除函数，并在字典二叉树中类似地实现了它。它确实很相似，唯一的区别是“key”值，但逻辑是相同的。

(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))))