Trees

Discussion of Common Lisp
Mercfh
Posts: 17
Joined: Tue Mar 30, 2010 3:39 pm
Location: Miami,FL

Trees

Post by Mercfh » Tue Mar 30, 2010 3:44 pm

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)
Last edited by Mercfh on Wed Apr 07, 2010 5:49 pm, edited 2 times in total.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Ternary Trees

Post by ramarren » Tue Mar 30, 2010 10:41 pm

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?

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Ternary Trees

Post by Jasper » Wed Mar 31, 2010 7:03 am

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

Mercfh
Posts: 17
Joined: Tue Mar 30, 2010 3:39 pm
Location: Miami,FL

Re: Ternary Trees

Post by Mercfh » Wed Mar 31, 2010 3:14 pm

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

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Ternary Trees

Post by Jasper » Thu Apr 01, 2010 8:05 am

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

Code: Select all

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

Mercfh
Posts: 17
Joined: Tue Mar 30, 2010 3:39 pm
Location: Miami,FL

Re: Ternary Trees

Post by Mercfh » Fri Apr 02, 2010 12:47 am

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)
Last edited by Mercfh on Wed Apr 07, 2010 1:08 am, edited 1 time in total.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Ternary Trees

Post by ramarren » Fri Apr 02, 2010 2:57 am

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.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Ternary Trees

Post by gugamilare » Fri Apr 02, 2010 1:00 pm

Jasper wrote:

Code: Select all

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

Mercfh
Posts: 17
Joined: Tue Mar 30, 2010 3:39 pm
Location: Miami,FL

Re: Ternary Trees

Post by Mercfh » Fri Apr 02, 2010 8:18 pm

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

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Ternary Trees

Post by ramarren » Fri Apr 02, 2010 11:30 pm

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

Post Reply