6
\$\begingroup\$

I took a simple BST implementation which is only really a set (i.e. just element, not key value), and decided to add a node count. I was translating this, which is explained here.

In particular the put method (below called bst-insert), but it's not the same thing, the difference in the languages seem large, plus the version below is non-destructive (functional?).

Two versions below. First the incorrect one, interesting because it shows where I started from, then the correct version which contains a fix to set node count from the newly created node, not by counting up the nodes on the old tree before the new node may have been inserted (which was the error).

I'm reasonably happy with the correct version, but happy for any further suggestions, critique and code review :)

(defstruct
  (node (:print-function
          (lambda (n s d)
            (format s "#<~A ~A ~A ~A>" (node-elt n) (node-l n) (node-r n) (node-count n)))))
  elt (l nil) (r nil) count)

(defun node-size (node)
  (if (null node)
      0
      (node-count node)))


; Incorrect version of bst-insert

(defun bst-insert (obj bst <)   (if (null bst)
      (make-node :elt obj :count 1)                       
      (let ((elt (node-elt bst)))
        (if (eql obj elt)
            bst                                           
            (if (funcall < obj elt)
                (make-node
                  :elt elt
                  :l (bst-insert obj (node-l bst) <)
                  :r (node-r bst)
                  ; error: we need node-size below not of node-l of parameter 'bst', as now, but
                  ; of left subtree of *this* node being creating now, as set in the lines above.
                  :count (+ (node-size (node-l bst)) (node-size (node-r bst)) 1)) ; <- INCORRECT
                (make-node             
                  :elt elt
                  :l (node-l bst)
                  :r (bst-insert obj (node-r bst) <)
                  :count (+ (node-size (node-l bst)) (node-size (node-r bst)) 1)))))))

The above code is wrong, and gives:

[9]> (setf bst (bst-insert 5 bst #'<))
#<6 #<5 NIL NIL 1> NIL 1>
[10]> (setf bst nil)
NIL
[11]> (setf bst (bst-insert 6 bst #'<))
#<6 NIL NIL 1>
[12]> (setf bst (bst-insert 5 bst #'<))
#<6 #<5 NIL NIL 1> NIL 1>    ; <- count for 6 should be 2, not 1.
[13]> 

Correct version:

(defun bst-insert (obj bst <)
  (if (null bst)
      (make-node :elt obj :count 1)                       
      (let ((elt (node-elt bst)))
        (if (eql obj elt)
            bst                                           
            (if (funcall < obj elt)
                (let ((new-l (bst-insert obj (node-l bst) <)))
                  (make-node
                    :elt elt
                    :l new-l
                    :r (node-r bst)
                    :count (+ (node-size new-l) (node-size (node-r bst)) 1))) ; <- CORRECT
                (let ((new-r (bst-insert obj (node-r bst) <)))
                  (make-node
                    :elt elt
                    :l (node-l bst)
                    :r new-r
                    :count (+ (node-size (node-l bst)) (node-size new-r) 1))))))))

gives

[14]> (setf bst nil)
NIL
[15]> (setf bst (bst-insert 6 bst #'<))
#<6 NIL NIL 1>
[16]> (setf bst (bst-insert 5 bst #'<))
#<6 #<5 NIL NIL 1> NIL 2> ; <- node count of root is now correctly 2.
[17]> 

Discussion

  1. First I forgot the 'extra' parens round let, hopefully I'll remember next time I get - LET: illegal variable specification that, even when you only have one expression pair in your let, you still must have 'extra' parens wrapping them as if they were a group.

  2. I tried moving the entire make-node into a let, but that got messy, bad idea.

  3. I also tried prog1, but since we need to update the node that's returned, that seemed wrong.

I'm more or less happy with the above, but interested in any improvements of style or even functionality if anyone is partial.

One thing I'm interested in getting toward in time is KD-trees, but seems to make sense to play with regular trees for a bit more first.

\$\endgroup\$
2
\$\begingroup\$

Overall looks good, so take below as a few ideas, nothing's really wrong with it.

Except using setf without a previous variable declaration, that's just not guaranteed to even work (assuming that's what the code snippet showed with (setf bst nil)).


I'm gonna try this on CCL:

Evaluating the structure definition gives me an unused warning for the d parameter of the node printing function - consider declaring it ignored to silence that: (declare (ignore d)).

(l nil) doesn't add much on top of l (same goes for (r nil)). Also consider using a more simple positional calling convention, after all the :elt, :l (which really could just be :left btw.) etc. gets kind of verbose:

(defstruct (node (:constructor make-node (elt count &optional l r)))
  elt count l r)

Also I've rotated the order of elements so that (make-node obj 1) is straightforward.

Okay, so bst-insert now:

Consider using cond for deep if blocks to reduce the level of indentation. I suppose here it doesn't help too much though.

eql can be simplified to eq here, that's sometimes important, here it's just for completeness' sake though. Edit: Jumped to quickly on that, eql is correct since there were integers in the example. For a generally usable tree you might want to make it possible to customise the equality test.

The rest of the body looks okay, a bit of reshuffling could possibly reduce the duplication a bit, but really it's all about clarity, how easy it is to discern what's happening and to detect any possible mistakes easily.

Thus, I'd arrive at this, perhaps:

(defun bst-insert (obj bst <)
  (if (null bst)
      (make-node obj 1)
      (let ((elt (node-elt bst)))
        (if (eq obj elt)
            bst
            (let* ((less-than (funcall < obj elt))
                   (old-l (node-l bst))
                   (old-r (node-r bst))
                   (new-l (if less-than (bst-insert obj old-l <) old-l))
                   (new-r (if less-than old-r (bst-insert obj old-r <))))
              (make-node
                   elt
                   (+ (node-size new-l) (node-size new-r) 1)
                   new-l
                   new-r))))))

Personally, I'd also go for long names, or really short ones. Like, either o or object; obj and elt just make me wonder what is meant most of the time. Note that elt is also a regular CL function, so e or element might be better.


Wrt. your other points:

  • There are of course macros to reduce the nesting for, say, let, but it's hardly a problem. Just remember that let can create multiple bindings, so grouping things makes sense.
  • prog1 is useful, but as you said, I don't see much value in using it here.
\$\endgroup\$
  • 1
    \$\begingroup\$ EQL can't be simplified to EQ. EQ effects are undefined for numbers and characters. The example uses numbers. \$\endgroup\$ – Rainer Joswig Oct 18 at 19:13
  • 1
    \$\begingroup\$ Fixed, thank you. \$\endgroup\$ – ferada Oct 18 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.