Trees
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)
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.
Re: Ternary Trees
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: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.
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:Can anyone explain how exactly this works?
Have you read Practical Common Lisp or Gentle Introduction to Symbolic Computation?Mercfh wrote:I've been doing some reading on Common Lisp (a few ebooks and the like for my university)
Re: Ternary Trees
Do you mean Ternary search tree? Seems that it is for strings, though. (Although same difference)Don't know much about them.
Re: Ternary Trees
Well this one if just for integers.Jasper wrote:Do you mean Ternary search tree? Seems that it is for strings, though. (Although same difference)Don't know much about them.
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
Re: Ternary Trees
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...)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...
Code: Select all
(defun get-bit (x n &key (ash-n (ash 1 n)))
(= (logand x ash-n) ash-n))
Re: Ternary Trees
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)
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.
Re: Ternary Trees
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.Mercfh wrote:but how do you know......where to put them
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.
-
- Posts: 406
- Joined: Sat Mar 07, 2009 6:17 pm
- Location: Brazil
- Contact:
Re: Ternary Trees
Or use logbitp, which is already in ANSI CL.Jasper wrote:Code: Select all
(defun get-bit (x n &key (ash-n (ash 1 n))) (= (logand x ash-n) ash-n))
Re: Ternary Trees
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
sorry Im so used a node only having 1 value, i dont see why you'd be storing 2 values in a node
Re: Ternary Trees
It says so in the very text of assignment you quoted!Mercfh wrote:U say the nodes can store up to 2 values? why 2 values. and can it be any value?
Seriously, try reading it. Doing a task is much simpler once you actually read the description. Sorry if this sounded snarky, but, well...Each node in a non-empty ternary tree is allowed to have either 1 or 2 values.