Hello,
Any rule of thumb as how to write a tree data structure for fast
"updating / traverse"?
For example, say we have a tree like:
a
b c d e
f g ......
Node a is parent of node b, c, d, e. And node b is the parent of node f
and g. etc.
Each node has a count (integer) there.
Now, if we have a new data like "abg", then we start at the root node
a, go down to node b, and then down to node g. And update their counts
along the way.
Suppose the tree will be "wide" (each node can have many children
nodes), and not "tall" (just several levels).
I use a hashtable in each node (see below) to keep the children
informatin (hash their id to their node), but this seems not fast
(based on my experience using other people's programs having the same
purpose).
class OneNode
{
int count;
Hashtable hash_ChildID_To_ChildNode;
}
Any idea of how to do it more quickly?
Thanks a lot and have a nice weekend!
PS: I am using Java for it. I have tried the Hashmap, which can save
less than 5% time, but still not good. I am thinking there may be some
better data structure than my method.
X-Google-Language: ENGLISH,ASCII-7-bit
Received: by 10.11.53.63 with SMTP id b63mr74908cwa;
Fri, 19 May 2006 19:32:59 -0700 (PDT)
X-Google-Token: lRuAywwAAAC_pU-KfAHRbxD8xF-icRYG
Received: from 68.78.131.97 by i40g2000cwc.googlegroups.com with HTTP;
Sat, 20 May 2006 02:32:58 +0000 (UTC)
From: "Kevin" <[EMAIL PROTECTED]>
To: "Algorithm Geeks" <algogeeks@googlegroups.com>
Subject: Best way for a tree data structure for fast updating?
Date: Fri, 19 May 2006 19:32:58 -0700
Message-ID: <[EMAIL PROTECTED]>
User-Agent: G2/0.2
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET
CLR 1.0.3705; .NET CLR 1.1.4322; FDM),gzip(gfe),gzip(gfe)
Mime-Version: 1.0
Content-Type: text/plain
Hello,
Any rule of thumb as how to write a tree data structure for fast
"updating / traverse"?
For example, say we have a tree like:
a
b c d e
f g ......
Node a is parent of node b, c, d, e. And node b is the parent of node f
and g. etc.
Each node has a count (integer) there.
Now, if we have a new data like "abg", then we start at the root node
a, go down to node b, and then down to node g. And update their counts
along the way.
Suppose the tree will be "wide" (each node can have many children
nodes), and not "tall" (just several levels).
I use a hashtable in each node (see below) to keep the children
informatin (hash their id to their node), but this seems not fast
(based on my experience using other people's programs having the same
purpose).
class OneNode
{
int count;
Hashtable hash_ChildID_To_ChildNode;
}
Any idea of how to do it more quickly?
Thanks a lot and have a nice weekend!
PS: I am using Java for it. I have tried the Hashmap, which can save
less than 5% time, but still not good. I am thinking there may be some
better data structure than my method.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
