Binary search tree obscure code...

Discussion of Common Lisp
Post Reply
megera
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm

Binary search tree obscure code...

Post by megera » Wed Oct 24, 2012 4:20 am

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

Konfusius
Posts: 62
Joined: Fri Jun 10, 2011 6:38 am

Re: Binary search tree obscure code...

Post by Konfusius » Wed Oct 24, 2012 6:07 am

The problem is your print-function which prints only the root node of the tree.

stackman
Posts: 28
Joined: Sat Oct 06, 2012 5:44 am

Re: Binary search tree obscure code...

Post by stackman » Wed Oct 24, 2012 7:17 am

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.

megera
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm

Re: Binary search tree obscure code...

Post by megera » Wed Oct 24, 2012 10:19 am

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

stackman
Posts: 28
Joined: Sat Oct 06, 2012 5:44 am

Re: Binary search tree obscure code...

Post by stackman » Thu Oct 25, 2012 2:41 am

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.

megera
Posts: 30
Joined: Wed Oct 10, 2012 1:34 pm

Re: Binary search tree obscure code...

Post by megera » Thu Oct 25, 2012 3:57 am

good, thanks again ;)

Post Reply