1
\$\begingroup\$

I'd like some input on my implementation of bst-range, which follows below.

Before we can get to bst-range, we first need some setup code to build the BST.

(You can imagine that node label count didn't exist if you want, as it's not used for range search).

Setup

(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 count (l nil) (r nil))

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

(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
                    :count (+ (node-size new-l) (node-size (node-r bst)) 1)
                    :l new-l
                    :r (node-r bst)))
                (let ((new-r (bst-insert obj (node-r bst) <)))
                  (make-node
                    :elt elt
                    :count (+ (node-size (node-l bst)) (node-size new-r) 1)
                    :l (node-l bst)
                    :r new-r)))))))

The above code was the subject of my earlier question and is working fine. It's assumed here.

Range search

I implemented bst-range by translating the code here (where it is referred to as the function keys), and described here under the heading "range search".

(defun bst-range (min max bst <)
  (if (null bst)
      nil
      (let ((elt (node-elt bst)))
        (when (funcall < min elt)
          (bst-range min max (node-l bst) <))
        (when (and (or (eql min elt)
                       (funcall < min elt))
                   (or (eql max elt)
                       (funcall < elt max)))
          (setf *result* (cons elt *result*)))
        (when (funcall < elt max)
          (bst-range min max (node-r bst) <)))))

It runs like this

(defparameter *bst* nil)                   ; [1]
(dolist (x '(1 6 3 7 21 40))
  (setf *bst* (bst-insert x *bst* #'<)))


[25]> (defparameter *result* nil)          ; [2]
*RESULT*

[26]> (bst-range 5 10 *bst* #'<)           ; [3]
NIL

[27]> *result*                             ; [4]
(7 6)

[28]> 

;; [1] first build a BST
;; [2] use global var to store result of range search (seems ugly)
;; [3] call the range search
;; [4] see the result
;;     Here we are searching for all the entries in the bst between
;;     5 and 10, which are, as we can see from what we inserted, just 6 & 7.

Questions

  1. Is there a nice way to accumulate the result via an optional parameter? I tried (and failed) on that, which is why I ended up with defparameter. Not certain the accumulator is the right path for this function though. Is it? If not, why?

  2. Would some datastructure for result other than a list be better here? If so, why?

Update

Here's another idea for bst-range, implemented via a higher order function.

(defun bst-traverse (fn bst)
  (when bst
    (bst-traverse fn (node-l bst))
    (funcall fn (node-elt bst))
    (bst-traverse fn (node-r bst))))


(defun bst-range (min max bst <)
  (bst-traverse (lambda (elt)
                  (when (<= min elt max)
                    (princ elt)))           ; [1]
                bst)) 

;; [1] We need to enqueue onto some ds here instead of princ.
;;     Wondering how best to organise this code...
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.