But, that's not important. What is important is that a hashtable provides O(1) performance for known keys, while providing O(N) performance for unknown keys. This compares with your basic tree that provides O(log N) performance for both known and unknown keys. Depending on the tree that performance can degrade e.g. AVL trees provide O(N log N) performance.
Anyway, all of the above is important because you don't appear to care about the order anyway. What you want is to find a node with a certain criteria e.g. the node at level 20. Going back to a previous note where I suggested using a string to represent a unique node and its place in the hierarchy, you can use a hashtable to store this string as a key. That way once you know the key you can get O(1) performance getting the node as well as the child nodes. And you will know the key since you will generate them in the first place.
Below is a simplistic example using a database. Assume you have the following data and hierarchy.
id name parent 1 foobar null 2 foo 1 3 bar 1 4 boo 3
Now you can represent the same information as follows.
id name hash 1 foobar 0001 2 foo 00010002 3 bar 00010003 4 boo 000100030004
Finding information is now very easy. Want to find the node at level three? Then do the following.
SELECT id, name FROM table WHERE Len(hash) = 12
Since each node has a hash that is its parent's hash concatenated with its id fixed to four digits then any node at level three would have to have a twelve digit hash. Want get all the children of bar?
SELECT id, name FROM table WHERE hash LIKE '00010003%'
Want a node's parent?
SELECT id, name FROM table WHERE hash = Left('00010002', Len('00010002') - 4)
Want to get the whole hierarchy in sorted order? You guessed it, just sort on the hash column.
As you can see, this method is quite easy to implement and very easy to query against. Additionally, indexing the hash column creates impressive performance. There is in fact only one issue to worry about; string length. If each node's fixed length hash of its id field is four digits long and the column is a varchar(8000) then of course you can only have a tree that is 2000 nodes wide and 10000 nodes tall. Changing the length of the fixed hash has a huge impact on the size of the tree. However, you aren't limited to just numbers. You can hash the id column using a base64 routine instead and lower the fixed length hash to three digits, which allows you to support 2666 nodes wide and 262144 tall.
-Matt
On Mar 1, 2004, at 9:46 PM, Joe Eugene wrote:
-Matt
I just looked at the BACFUG archive and it only has the PPT
Thanks for looking into this.
you want anyway. I think you want a hashtable.
I belive Hashtable takes the "natural order" of elements, Not sorted, cannot accomodate a custom order and is mostly supported only for backward compatibility just like Vector.
While a TreeMap lets you do a Custom Order (In this case levels) by using
the Comparator and lets you pull random levels using subMap() Or tailMap().
e.g. tailMap("123567") will give all the children of this Object Map.
Joe Eugene
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
Behalf Of Matt Liotta
Sent: Monday, March 01, 2004 9:00 PM
To: [EMAIL PROTECTED]
Subject: Re: [CFCDev] OT: A Good Data Structure for a Large Binary Tree
I just looked at the BACFUG archive and it only has the PPT; no CFML
code. Right now I am out of town, so I can't access it any other way.
However, based on your other message I don't think using a tree is what
you want anyway. I think you want a hashtable.
-Matt
On Mar 1, 2004, at 8:51 PM, Joe Eugene wrote:
Matt,
I presented an AVL tree
Can you post or send me a link to your implementation?
Thanks, Joe Eugene
-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Matt Liotta Sent: Monday, March 01, 2004 8:43 PM To: [EMAIL PROTECTED] Subject: Re: [CFCDev] OT: A Good Data Structure for a Large Binary Tree
As part of a presentation to BACFUG, I presented an AVL tree implementation written in CFML.
On Mar 1, 2004, at 8:34 PM, Paul Kenney wrote:
Joe,
Do you want a CF solution to your tree problem? I haven't really
seen
any
implementations for this kind of thing done in CF... Although someone
might
have done it. Also, what CF version are you targeting? Personally,
I'd go
with the Java API if I could. Chances are good that it will probably
work
better with less work than a CF version.
Do you have the ability to add jar files into the class path on the
CF
server? If not, definitely go with the JDK.
Paul Kenney WebMaster, CorporateWarriors.com 916-663-1963
-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Joe Eugene Sent: Monday, March 01, 2004 5:11 PM To: [EMAIL PROTECTED] Subject: RE: [CFCDev] OT: A Good Data Structure for a Large Binary Tree
Anybody can help brain storm ideas?
Thanks, Joe Eugene
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
Behalf Of Joe Eugene
Sent: Sunday, February 29, 2004 1:44 PM
To: cfczone; CF-Talk
Subject: [CFCDev] OT: A Good Data Structure for a Large Binary Tree
I am trying to solve a Binary Tree data structure problem, i think
this
can be done from a DataBase Perspective with relations but then that
might involve doing something like a matrix to develop the relations
between nodes.
The other thought i have is solve the problem by using some
native(Java/C++)
data Structure (Binary Tree /TreeMap) and store keys of the database
structure
as keys of the Binary Tree... that might relate to a simple select.
Any ideas are much appreciated.
Thanks, Joe Eugene
---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]
---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]
---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available atwww.mail-archive.com/[EMAIL PROTECTED] ---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]
---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available atwww.mail-archive.com/[EMAIL PROTECTED] ---------------------------------------------------------- You are subscribed to cfcdev. To unsubscribe, send an email to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]
----------------------------------------------------------
You are subscribed to cfcdev. To unsubscribe, send an email
to [EMAIL PROTECTED] with the words 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
An archive of the CFCDev list is available at www.mail-archive.com/[EMAIL PROTECTED]
