Sign in to follow this  
yitzle

A "trie"

Recommended Posts

How do I store a valuie in a *branch* of a trie opposed to in the node (like in a tree)? As defined by assignment sheet (I'm not in this course...): "A trie (pronounced “try”) is a tree structure for storing information. However, unlike the typical binary tree structures that we examine in class, a trie is a multi-branch tree that stores its data a little differently. Tries are similar in that each node contains branches to other nodes, but different in that the branches of the tree are responsible for storing the tree’s data. [picture] As mentioned earlier, the trie nodes don’t store any data values, just the branches leading from the node. However, that doesn’t mean that the trie isn’t storing data. In fact, this trie in the diagram shown above is storing the words “a”, “at”, “ate”, “on”, “one”, “out”, “me”, and “my”. You can discover each of these words by starting at the root and traversing down the branches of the tree. Whenever a path from the root encounters a light-coloured node, that path has traced out a possible word. All the words stored in the trie can be found this way, by tracing all the paths from the root to a light-coloured node. This isn’t to say that there aren’t other words in the English language, just that these are the only words represented by this structure." Or see Wiki: http://en.wikipedia.org/wiki/Trie

Share this post


Link to post
Share on other sites
I think, at first glance, each node would just need a bunch of 'char' values, with each one associated with a pointer to another node. You could use std::map, for example, to keep an association between char's and node ptr's per node.

I think what they meant by "no node in the tree stores the key associated with that node" was that you don't need to store the whole string in each node. Associating a char with a pointer essentially associates a char with a branch (though not explicitly stored in any kind of "branch" data structure).

Let me know if that makes sense.

Share this post


Link to post
Share on other sites
The goal of this is to allow highly compressed versions of the trie, for instance a trie storing intention and inversion as such:


o A
|
in
|
o B
/ \
/ \
vers tent
\ /
\ /
o C
|
ion
|
o D


Information is not related associated to nodes, but to node pairs: (AB) is "in", (BC) is "vers" and "tent". This would for instance be done by creating a node-information association in each node.

Share this post


Link to post
Share on other sites
Hmm, I have never seen a trie come back together, as in that example. Interesting...

For a project, I used tries once to store '0' and '1' (binary trie). I never considered bringing common suffixes back together.

Share this post


Link to post
Share on other sites
Bringing them back? Wow!
Um, I thought of each node having an arrays 26 long stroing the pointers. 'a' corresponding to aray[0], or use array[char-67]...
But I'm not sur about that bit about not storing data in nodes but in branches...

Share this post


Link to post
Share on other sites
Quote:
Original post by yitzle
But I'm not sur about that bit about not storing data in nodes but in branches...


You don't need to store the whole string-so-far in each node, as shown in the somewhat misleading diagram:

http://en.wikipedia.org/wiki/Image:Trie_example.png

The action of branching to one other node is what determines the string at a given node. So yeh, your idea of an array of 26 ptr's would be fine. Better would be a dynamic array that is associative, or some such thing (to save memory). (std::map)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this