Delete smallest element in a BST (translate C to Lisp)

Question

I've been trying for more than an hour to translate the following C code to Lisp to fix the bst-remove function in the BST code in Paul Graham's book ANSI Common Lisp (which as explained in the errata to that book, is broken) and I am completely stumped.

I've been trying to write it destructively (also non-destructively), and run into the problem of having to detect the actual smallest node I want to operate on not from the final node, but one level above, so that I can reassign it. That's kind of where pointers come in in the C version, and I don't know what I'm doing in Lisp to try to achieve a similar end.

You may already know this as it is part of a standard bst remove function, but as per below, the requirement is to replace the smallest node with its right child.

I'm not too bothered about returning the min. In fact, if we write this non-destructively, then what we want to return is the new tree minus the min element, not the min (never mind returning multiple values).

So, I'm totally stumped on this and have given up.

ETYPE deletemin(TREE *pT) 
{
    ETYPE min;

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

Source for above: p264 in this pdf.

Here is the struct concerned for the Lisp version

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

Let me know if you want me to post any more of the rest of the BST code.

Idea (non-working) (see discussion in comments):

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

What I'd really like though is a non-destructive version

guess; one may be able to copy over the slots of the right sub-object, to the current object... — Rainer Joswig
@RainerJoswig I went down that path and I think the reason it didn't work was that if the right sub-object is null, then the object itself needs to be set to null. But doing a (setf bst nil) in a base case didn't affect the calling function. So... is this a question of lexical vs dynamic variables? — mwal
@RainerJoswig I've added that non-working attempt to the OP above for reference. — mwal
I've copied, compiled and tested the bst code from p.71 of 7chan.org/pr/src/ANSI_Common_Lisp_-_Paul_Graham.pdf . So far as I can tell, it works fine in LispWorks, GCL, CCL and SBCL. Can you provide a link to that errata you are mentioning in your question, as there are none mentioned in my link? Can you also provide the full code where the error occurs? I can copy my code in an answer, if you wish. — peter.cntr

Sylwester Sylwester · Accepted Answer · 2019-07-10T01:31:43

Immutable and functional version, very much like the version in the book but deletes the lowest value only:

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

A version that may mutate tree. As with similar CL functions you should use the returned value.

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

Delete smallest element in a BST (translate C to Lisp)

1 Answers