Page 1 of 1

Binary search tree obscure code...

Posted: Wed Oct 24, 2012 4:20 am
by megera
HI
I have a problem of understand an example code of Binary search trees to store an object that I’m studying on a CL guide ANSI…
First we create a structure :

Code: Select all

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

well, after that we define a bst-insert func for store an object in a tree:

Code: Select all

(defun  bst-insert (obj bst <)
            (if  (null  bst)
                (make-node :elt obj)
                (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))
                             (make-node
                                 :elt elt
                                 :r (bst-insert obj (node-r bst) <)
                                 :l (node-l bst)))))))

Now, we initialize “nums”

(setf nums nil )

And iterate on a list of numbers to create Tree…

Code: Select all

(dolist ( x '( 5 8 4 2 1 9 6 7 3))
             (setf nums ( bst-insert x nums #'<)))     

But we obtain NIL and if I call nums it returns only #<5> but not a TREE as book explains…

But ther’re many steps that are obscure for me:
For example the function never create an istance of node structure…infact “(make-node :elt obj)” set a value for elt slot but not create an instance of node!!…then in “else” conditions how function can call: (let ((elt (node-elt bst)))”..????? bst isn’ t an instance of node!!!it’s like :
(let((elt (node-elt #<5>…) that raise error!!…for me it’s obscure code, can someone help me with??
Thanks in advance

Re: Binary search tree obscure code...

Posted: Wed Oct 24, 2012 6:07 am
by Konfusius
The problem is your print-function which prints only the root node of the tree.

Re: Binary search tree obscure code...

Posted: Wed Oct 24, 2012 7:17 am
by stackman
Everything is fine in the code, you're just confused by what the call to a struct returns.
When you eval nums at the repl, the :print-function defined by defstruct is called and returns
a string of the form #<5>, where 5 is the element stored in the main node of your tree.

Graham returns a string of the form #<...> precisely because it is an error to evaluate a form
starting by #< at the repl. The printed form of num is not a tree object but just an indication
of what is in the main node of the tree, not meant for consumption at the repl.

You can however call the three functions defined by defstruct, namely node-elt, node-r and node-l,
on a given node structure, to access the datas stored in the three slots of the struct
(for nums, the number 5, and two other node structures) and print recursively
the elements stored in the tree.

Code: Select all

(node-elt nums)
   => 5                     ;; 5 is stored in the first node of the tree
(node-l nums)
   => #<4>                  ;; the left slot of nums contains the number 4
(node-r nums)
   => #<8>                  ;; the right slot of nums contains the number 8
(node-l (node-l nums))
   => #<2>                  ;; we get the printed form of the left node of the left node of nums


This can be represented as

Code: Select all

             5
          /    \
         4      8
       / \
     2    ...
If you are still confused, I suggest reading the section "common lisp structures" in chapter 9
of land-of-lisp, which is more friendly to beginners.

Re: Binary search tree obscure code...

Posted: Wed Oct 24, 2012 10:19 am
by megera
hooo, perfect stackman!!now it's all clear...thanks very much!!!
my problem was also in "visualization" the correct structure of a binary tree...
well, for example after five iterations "nums" become a sequence of nested lists like this: (5, (4,(2,1,NIL) NIL) 8)...where first item in list is a node, second left child and third right child),;
then the bst-insert recursive function create a new istance of node structure with make-node --> sub-nodes of root relatively to a given "ordering function" ( < in this example) ;finally I hope you understand it !!!!!

ps. I'm following "Ansi CL" as guide book... You think that "Land of Lisp" can be a better choise for a beginner like me??..if yes I can also buy it;
but so far with "ANSI CL" all seems ok, the synthax seem quite simple...but with semantic I have some problems (as in this case) becouse Graham seems very coincide and my english is very poor and probably I'm not so much deft!! :mrgreen: :mrgreen: :mrgreen:

thanks for your help stack and also to Konfusius for his suggestion :D

Re: Binary search tree obscure code...

Posted: Thu Oct 25, 2012 2:41 am
by stackman
ps. I'm following "Ansi CL" as guide book... You think that "Land of Lisp" can be a better choise for a beginner like me??..
Graham's Ansi CL is fine. The book Land of lisp is written in a very different style. Have a look at its website and see if you find it appealing.

Re: Binary search tree obscure code...

Posted: Thu Oct 25, 2012 3:57 am
by megera
good, thanks again ;)