时间戳

首页 > 解决方案 > 删除 BST 中的最小元素（将 C 转换为 Lisp）

common-lisp - 删除 BST 中的最小元素（将 C 转换为 Lisp）

问题描述

我已经尝试了一个多小时将以下 C 代码转换为 Lisp，以修复bst-removePaul Graham 的书 ANSI Common Lisp 中的 BST 代码中的函数（正如那本书的勘误表中所解释的那样，已损坏），我是完全难住了。

我一直在尝试破坏性地（也是非破坏性地）编写它，并且遇到了必须检测我想要操作的实际最小节点的问题，而不是从最终节点，而是上一层，以便我可以重新分配它。这就是指针在 C 版本中出现的地方，我不知道我在 Lisp 中做了什么来尝试达到类似的目的。

您可能已经知道这一点，因为它是标准 bst 删除功能的一部分，但如下所示，要求是replace the smallest node with its right child.

我不太担心返回分钟。事实上，如果我们非破坏性地编写这个，那么我们想要返回的是新树减去 min 元素，而不是 min（不要介意返回多个值）。

所以，我完全被这件事难住了，已经放弃了。

ETYPE deletemin(TREE *pT) 
{
    ETYPE min;

    if ((*pT)->leftChild == NULL) { 
        min = (*pT)->element; 
        (*pT) = (*pT)->rightChild; 
        return min;
    } 
    else
        return deletemin(&((*pT)->leftChild));
}

以上来源：此pdf中的p264 。

这是有关 Lisp 版本的结构

(defstruct (node 
  elt (l nil) (r nil))

如果您希望我发布更多 BST 代码的其余部分，请告诉我。

想法（非工作）（见评论中的讨论）：

(defun delete-min (bst)
  (if (null (node-l bst))
      (if (node-r bst)
          (progn
            (setf (node-elt bst) (node-elt (node-r bst)))
            (setf (node-l   bst) (node-l   (node-r bst)))
            (setf (node-r   bst) (node-r   (node-r bst))))
          (setf bst nil))   ; <- this needs to affect the var in the calling fn
      (delete-min (node-l bst))))

我真正想要的是非破坏性版本

标签： common-lispbinary-search-tree

解决方案

不可变和功能版本，非常像书中的版本，但只删除了最低值：

(defun bst-remove-min (bst)
  (cond ((null bst) nil)
        ((null (node-l bst)) (node-r bst))
        (t (make-node :elt (node-elt bst)
                      :l (bst-remove-min (node-l bst)) 
                      :r (node-r bst)))))

可能会改变树的版本。与类似的 CL 函数一样，您应该使用返回值。

(defun n-bst-remove-min (bst)
  (when bst
    (loop :for p := c
          :for c := bst :then child
          :for child := (node-l c)
          :unless child
            :if p
              :do (setf (node-l p) (node-r c))
                  (return bst)
            :else
              :do (return (node-r c)))))

推荐阅读