Realizing tables via the Tree ADT
Generic Usenet Account
I have a need to realize a table structure (with index columns and
value columns) using the Tree Abstract Data Type. Does anyone have an
idea how to proceed? Does it even make sense?
Any help will be appreciated.
Thanks,
Gus
Jonathan Campbell
[I'm replying to all the n.g.'s in the original post; apologies if that
annoys anyone, I'm unsure of the etiquette of choosing which to reply to.]
I know you don't specify any language, but Google <stl map> and you will
get information on C++'s std::map.
Looking further into your mind; maybe, by Tree, what is meant is a
binary search tree (BST)? A BST is a container which permits fast, O(log
^2 N), search for an element.
Normally, a map will be implemented using some sort of BST.
A plain BST will have only a data element (plus pointers or references)
in its nodes.
If you make the node contain a record (C, C++ struct, Java class), often
called 'pair', which contains a key (index?) and a value, and you make
it search on the key, then you have a map --- a fast lookup table, which
is possibly what you want.
If you set about implementing it, and you have already the BST ADT, then
create a Pair class with key and value. Provide a less-than function /
operator that operates on the key; substitute a Pair object for your
current element, ... and you are nearly done.
Incidentally, don't go looking for C++ std::tree or std::bst, there
isn't either, nor any explicit tree collection in the C++ standard
library. Not sure about Java.
Best regards,
Jon C.
--
Jonathan Campbell www.jgcampbell.com BT48 UK
user923005
wrote:
> Hi,
>
> I have a need to realize a table structure (with index columns and
> value columns) using the Tree Abstract Data Type. Does anyone have an
> idea how to proceed? Does it even make sense?
A tree is usually used as an access method -- used to navigate data.
The thing that is accessed can be anything, including a table row.
I would go about it this way:
1. Create a column object. It should be generic enough to describe
itself and able to take on any data type. A struct or class should do
nicely.
2. Create a row object. It should be composed of a list of columns.
A linked list makes sense in this context. An array is a less
flexible alternative.
3. Create a table object. It should be composed of row objects. A
doubly linked list so you can navigate forward and backwards is one
possibility. A vector of rows is another.
4. Use your tree to navigate special collections of columns from the
table object (say -- columns 1,3, and 7 might be one possibility).
You should be able to define the direction of navigation (ascending or
descending) by each column.
Used in this way, it makes sense (at least, to me).
Martin Michael Musatov
Gus,
For some inspiration and brainstorming there are some really good
fresh out of the box ideas on table solutions in this (TSP) example:
I hope this gives you some ideas to approach the problem with a fresh
perspective and you are able to find out all the information you
require to succeed!
Best wishes with your work!
Kindly,
Martin Musatov
Richard Heathfield
>
>
> Generic Usenet Account wrote:
>> Hi,
>>
>> I have a need to realize a table structure (with index columns
>> and
>> value columns) using the Tree Abstract Data Type. Does anyone
>> have an
>> idea how to proceed? Does it even make sense?
>>
>> Any help will be appreciated.
>>
>> Thanks,
>> Gus
> Gus,
>
> For some inspiration and brainstorming there are some really good
> fresh out of the box ideas on table solutions in this (TSP)
> example:
>
> http://MeAmI.org/blog/?p=83
Personally, I find that page unreadable because the text on the
images is way too small. Perhaps you would be so kind as to explain
these fresh out of the box ideas in a way that we can all
understand even if we don't have the ability to read FlySpeck-3?
> I hope this gives you some ideas to approach the problem with a
> fresh perspective and you are able to find out all the information
> you require to succeed!
It may have done, because the OP may have super-human eyesight. But
if I'd asked the same question and you'd given me the same answer,
I'd have dismissed your answer as a crank answer. Why would that
have been a mistake?
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
William Elliot
> [I'm replying to all the n.g.'s in the original post; apologies if that
> annoys anyone, I'm unsure of the etiquette of choosing which to reply to.]
>
Replying to all is correct because you do not know from which
newsgroup OP is posting nor do you know through which newsgroups
others interested in the thread, are participating.
Jonathan Campbell
> Generic Usenet Account wrote:
>> Hi,
>>
>> I have a need to realize a table structure (with index columns and
>> value columns) using the Tree Abstract Data Type. Does anyone have an
>> idea how to proceed? Does it even make sense?
>>
>> Any help will be appreciated.
>>
[...]
I could have written my first answer more clearly and crisply.
A binary search tree (BST) is a commonly used (*) implementation of a
'set'; the BST allows O(log N) performance for 'find' and 'insert'.
(*) Since plain BSTs can become unbalanced, in practice, you will find
that library implementations use BSTs with modifications to avoid
unbalancing --- such as AVL trees, Red-Black trees.
You will find a Set class in Java.
A 'map' implements a mathematical 'map' or 'function'. Hence we need a
'set' (for the domain) and we would like fast lookup from a 'key' (in
the domain) to a value (in the range).
That would be my explanation of the role of a 'Tree' ADT in the
implementation of a 'table'.
Jon C.
--
Jonathan Campbell www.jgcampbell.com BT48, UK.
Martin Michael Musatov
Because the OP may have super-human eyesight.
P=Musatov=OP=NP+1
Richard Heathfield
> Richard Heathfield wrote:
>> Martin Michael Musatov said:
<snip>
>>
>> > I hope this gives you some ideas to approach the problem with a
>> > fresh perspective and you are able to find out all the
>> > information you require to succeed!
>>
>> It may have done, because the OP may have super-human eyesight.
>> But if I'd asked the same question and you'd given me the same
>> answer, I'd have dismissed your answer as a crank answer. Why
>> would that have been a mistake?
>
> Because the OP may have super-human eyesight.
In other words, it wouldn't have been a mistake. Thanks for the
heads-up.
Chris M. Thomasson
news:9JOdnTyrrNyC4ILX...@bt.com...
> Martin Michael Musatov said:
>
>>
>>
>> Generic Usenet Account wrote:
>>> Hi,
>>>
>>> I have a need to realize a table structure (with index columns
>>> and
>>> value columns) using the Tree Abstract Data Type. Does anyone
>>> have an
>>> idea how to proceed? Does it even make sense?
>>>
>>> Any help will be appreciated.
>>>
>>> Thanks,
>>> Gus
>> Gus,
>>
>> For some inspiration and brainstorming there are some really good
>> fresh out of the box ideas on table solutions in this (TSP)
>> example:
>>
>> http://MeAmI.org/blog/?p=83
>
> Personally, I find that page unreadable because the text on the
> images is way too small. Perhaps you would be so kind as to explain
> these fresh out of the box ideas in a way that we can all
> understand even if we don't have the ability to read FlySpeck-3?
Are these easier for you to read:
http://meami.org/blog/wp-content/uploads/2009/05/1.png
http://meami.org/blog/wp-content/uploads/2009/05/2.png
http://meami.org/blog/wp-content/uploads/2009/05/3.png
http://meami.org/blog/wp-content/uploads/2009/05/4.png
http://meami.org/blog/wp-content/uploads/2009/05/5.png
http://meami.org/blog/wp-content/uploads/2009/05/6.png
http://meami.org/blog/wp-content/uploads/2009/05/7.png
http://meami.org/blog/wp-content/uploads/2009/05/8.png
http://meami.org/blog/wp-content/uploads/2009/05/9.png
?
Richard Heathfield
> "Richard Heathfield" <r...@see.sig.invalid> wrote in message
> news:9JOdnTyrrNyC4ILX...@bt.com...
<snip>
>>
>> Personally, I find that page unreadable because the text on the
>> images is way too small. Perhaps you would be so kind as to
>> explain these fresh out of the box ideas in a way that we can all
>> understand even if we don't have the ability to read FlySpeck-3?
>> [...]
>
>
> Are these easier for you to read:
Vastly. Thank you. I'll take another look when I'm less tired.
(Presumably those URLs will persist long enough.)
Martin Michael Musatov
Thank you. Martin Musatov's proof NP=P. Proceed.
Martin Michael Musatov
Chris. M,
Just a note to say thank you kindly for automatically generating these
links to MeAmI.org.
Also, this is an invite to the programming community. If you want to
use Google with no ads and *slightly* better results search with
http://MeAmI.org. If you want to see an example of how the results
improve Google search visit http://MeAmI.org/blog and click on the
"About MeAmI" link. (Note: please disregard the WikiWikiWeb, I had it
up but it got killed by spam bots. I even wiped the server and did a
clean MySql install and it just gets taken over immediately with
strange ads for "Las Vegas" and foreign airfare - gotta love the
webocracy!!!)
Best and thanks again,
Martin Musatov
Screenwriter
"Crank", "Couch boy", "Troll", Founder MeAmI.org
:)
Martin Michael Musatov
Well, what if the OP were completely blind? Brief aside: does the
paper http://arxiv.org/pdf/0906.0129v1 prove NP=P? If the paper
http://arxiv.org/pdf/0906.0129v1 proves NP=P reply with (1). If the
paper http://arxiv.org/pdf/0906.0129v1 does not prove NP=P reply with
(2). If the paper http://arxiv.org/pdf/0906.0129v1 ...
Martin Michael Musatov
I own the site. The URL's will be available indefinitely. I eagerly
await your response!
CBFalconer
The real problem being that the OP failed to set a follow-up to the
appropriate newsgroup.
--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.