Trees

Hi Im new to the forums and new to Common Lisp in general.
I've been doing some reading on Common Lisp (a few ebooks and the like for my university) but I figured i'd come here and maybe get some helpful information.

Basically my assignment (it's not due for awhile, but figured i better get started early) is to Make a Trees using Common Lisp.

basically it reads in a series of integers from a text file (data.txt) for example.


Can anyone explain how exactly this works? and what would be the easiest way to go about this (or if it's even easy to do?)
I've read a little bit on Trees on wiki and such..but theirs unfortunately not a whole lot of "simple" explanations for them. Any hints/tips at how to go about this would be wonderful. (hopefully it's not too hard of a thing to do, the "concept" seems simple enough)

Mercfh wrote:I've read a little bit on Ternary Trees on wiki and such..but theirs unfortunately not a whole lot of "simple" explanations for them.

A ternary tree is just a tree where each node has three children. It says so in the first paragraph of Wikipedia article. How could it be any simpler? And there isn't anything more. Unless you mean something more complex than a raw tree.

Mercfh wrote:Can anyone explain how exactly this works?

Why do so many people just show a name and an example? If your assignment doesn't contain a specification more formal than that, then request one. If it does, then read it, and only if you still don't understand, ask question about it. As it is, there are quite many possible transformations from a flat list of elements to a cons cell representation of a ternary tree, and I doubt that guessing which one your assignment means is either a good idea or interesting.

Mercfh wrote:I've been doing some reading on Common Lisp (a few ebooks and the like for my university)

Have you read Practical Common Lisp or Gentle Introduction to Symbolic Computation?

Do you mean Ternary search tree? Seems that it is for strings, though. (Although same difference)Don't know much about them.

Jasper wrote:Do you mean Ternary search tree? Seems that it is for strings, though. (Although same difference)Don't know much about them.

Well this one if just for integers.
and the example he gave was literally what I have.

I guess ill need to email him specifiying how he wants to sort each one.

btw the book im reading is Practical Common Lisp

You could just follow the wikipedia description; it being a tree having all the possible letters on each node, and take the bits to be letters.(Implemented with a get(integer) and (setf get)(set-to integer) The following gets the nth bit:(Not perfect.. where is bit shift...)

(defun get-bit (x n &key (ash-n (ash 1 n)))
  (= (logand x ash-n) ash-n))

However, i don't really see how your example input list is supposed to be used to get the output list.. And how to exactly do it depends, is it supposed to count how often it sees some integer, is it supposed to only give true/false for each integer, or is it supposed to look up an object based on an integer...

Might be easier to just quote what our assignment says



it also says we must use "lists" to represent nodes of a tree....

Not exactly sure what he means by all this though. im assuming we use each node to choose the direction of the next value? I do know we print the tree after each insertion.
so it's like:
insert element
print tree
insert element
print tree.

and so on.
So i'd assume I get the elements one at a time and put them into the tree. but how do you know......where to put them because the wikipedia article is VERY unhelpful to me (it's so small)

Mercfh wrote:but how do you know......where to put them

It is a ternary search tree. It says in the assignment you quoted where to put them. What is unclear to you in that? A ternary tree node can have up to two values and three children. The elements you are inserting are the values. You take a value you want to insert, and then go though the tree in the way described until you find a node with zero or one values, and insert it there.

The list requirement actually makes this a bit tricky, especially if the example is supposed to be normative, since the format is a little weird. There are no actual lists in Common Lisp, only chains of cons cells, which means that side effecting them has a number of corner cases. I would recommend to write the code functionally, that is, without side effects, and reconstruct the tree after every insertion. This is a naturally recursive problem, as well.

I have written an implementation to check if I understood how this is supposed to work, and it is only 36 lines, and 13 of those is a function to convert from a format which makes sense to the one used in the example, so this is not hard. What you need is a recursive 'insert' function, which takes a value and a node. It has three primary cases, where the node is empty, ie. NIL, when it has one value, and the recursive case when it has two values and have to construct a new child node.

Jasper wrote:

(defun get-bit (x n &key (ash-n (ash 1 n)))
  (= (logand x ash-n) ash-n))

Or use logbitp, which is already in ANSI CL.

U say the nodes can store up to 2 values? why 2 values. and can it be any value?

sorry Im so used a node only having 1 value, i dont see why you'd be storing 2 values in a node

Mercfh wrote:U say the nodes can store up to 2 values? why 2 values. and can it be any value?

It says so in the very text of assignment you quoted!

Each node in a non-empty ternary tree is allowed to have either 1 or 2 values.

Seriously, try reading it. Doing a task is much simpler once you actually read the description. Sorry if this sounded snarky, but, well...

Ramarren wrote:

Mercfh wrote:U say the nodes can store up to 2 values? why 2 values. and can it be any value?

It says so in the very text of assignment you quoted!

Each node in a non-empty ternary tree is allowed to have either 1 or 2 values.

Seriously, try reading it. Doing a task is much simpler once you actually read the description. Sorry if this sounded snarky, but, well...

Ok I did some more research of Terenary trees and it makes more sense. Dont worry u dont sound snarky I know it can be frustrating lol but this is my first time using lisp so It's a bit confusing. But i got the atom reading part done at least yay.

I just have a tad bit of Dyslexia so when I read stuff (sometimes even 15 times) I wont exactly "get it" always because words do not always come together in the same way. (it makes coding a complete pain ahahah)

(defun read-setup (filename)
(with-open-file (stream filename)
    (loop for line = (read stream nil 'end)
          until (eq line 'end)           
          do (print (list (coerce line 'integer)
 )     
     )     
     )
)
)

I know it's small but this should work right? putting them into a single list unless there is a better way.

Mercfh wrote:

Ramarren wrote:

Mercfh wrote:U say the nodes can store up to 2 values? why 2 values. and can it be any value?

It says so in the very text of assignment you quoted!

Each node in a non-empty ternary tree is allowed to have either 1 or 2 values.

Seriously, try reading it. Doing a task is much simpler once you actually read the description. Sorry if this sounded snarky, but, well...

Ok I did some more research of Terenary trees and it makes more sense. Dont worry u dont sound snarky I know it can be frustrating lol but this is my first time using lisp so It's a bit confusing. But i got the atom reading part done at least yay.

I just have a tad bit of Dyslexia so when I read stuff (sometimes even 15 times) I wont exactly "get it" always because words do not always come together in the same way. (it makes coding a complete pain ahahah)

(defun read-setup (filename)
(with-open-file (stream filename)
    (loop for line = (read stream nil 'end)
          until (eq line 'end)           
          do (print (list (coerce line 'integer)
 )     
     )     
     )
)
)

I know it's small but this should work right? putting them into a single list unless there is a better way.

That implementation will work I think for an assignment like this. you are basically going to want to put the Atoms as they are called in an initial list. Then make the initial Tree parameters. You will need an insert function and then a print function. Although the default print in lisp will do the printing you will need.

gugamilare wrote:Or use logbitp, which is already in ANSI CL.

I did look for such a function, but i couldn't find it.. I think i am probably still missing a bunch of such functions... I'll try look at topical references next time.

Jasper wrote:

gugamilare wrote:Or use logbitp, which is already in ANSI CL.

I did look for such a function, but i couldn't find it.. I think i am probably still missing a bunch of such functions... I'll try look at topical references next time.

Try inspecting all the functions which begin with "log", ANSI CL have all sorts of bitwise operations. Take a look also at ldb and dpb.

Thanks everyone for your help. I FINALLY understand how the tree works.

It's pretty simple when I got down to it. I got a create-tree function set up. and it seems to work no errors so far. just understanding the concept was the hardest part.
I also got an insert function. my print function isn't working right now. it prints.........stuff, but it's all out of whack, but I got plenty of time to figure that out.

Just wanted to thank everyone for helping me understand it