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
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?
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...