help with my recursive trie search

C

chuck

Hello,
I wrote a simple Trie class that creates a Trie structure correctly
from character array. It will correctly recurisivley print the trie
correctly too, albeit not sorted.

The trie structue is a linked lists structure. Each node has two
pointers, next(sibling) and link(children).

I adapted the same structure that my print trie method uses to search
the trie for a particular integer index and want to return the trie
node if the index is found. The search seems to stop the recursion
when it finds the node, but returns null. The only node it correctly
find is the root.

public TrieNode findNodeIndex(TrieNode currentNode, int i){
// if(currentNode.index == i) return currentNode;
if(currentNode.link != null) findNodeIndex(currentNode.link, i);
//System.out.println( currentNode);
if(currentNode.index == i) return currentNode;
if(currentNode.next != null) findNodeIndex(currentNode.next, i);
//if(currentNode.index == i) return currentNode;
return null;
}

I have tried putting the test in various places without success, any
ideas why this fails?

If it helps i put Trie.java here
http://pastebin.ca/721376

and the test file, trietest.java here
http://pastebin.ca/721378

any help is appreciated
Chuck
 
B

Behrang

Hello,
I wrote a simple Trie class that creates a Trie structure correctly
from character array. It will correctly recurisivley print the trie
correctly too, albeit not sorted.

The trie structue is a linked lists structure. Each node has two
pointers, next(sibling) and link(children).

I adapted the same structure that my print trie method uses to search
the trie for a particular integer index and want to return the trie
node if the index is found. The search seems to stop the recursion
when it finds the node, but returns null. The only node it correctly
find is the root.

public TrieNode findNodeIndex(TrieNode currentNode, int i){
// if(currentNode.index == i) return currentNode;
if(currentNode.link != null) findNodeIndex(currentNode.link, i);
//System.out.println( currentNode);
if(currentNode.index == i) return currentNode;
if(currentNode.next != null) findNodeIndex(currentNode.next, i);
//if(currentNode.index == i) return currentNode;
return null;

}

I have tried putting the test in various places without success, any
ideas why this fails?

If it helps i put Trie.java herehttp://pastebin.ca/721376

and the test file, trietest.java herehttp://pastebin.ca/721378

any help is appreciated
Chuck

Hi Chuck,

You are returning from findNodeIndex too early. I have posted the
corrected findNodeIndex here:

http://pastebin.ca/721497

Also, in English, it is spelled "Tree", not "Trie" ;-)

-Behrang
 
M

Matt Humphrey

| > Hello,
| > I wrote a simple Trie class that creates a Trie structure correctly
| > from character array. It will correctly recurisivley print the trie
| > correctly too, albeit not sorted.
| >
| > The trie structue is a linked lists structure. Each node has two
| > pointers, next(sibling) and link(children).
| >
| > I adapted the same structure that my print trie method uses to search
| > the trie for a particular integer index and want to return the trie
| > node if the index is found. The search seems to stop the recursion
| > when it finds the node, but returns null. The only node it correctly
| > find is the root.
| >
| > public TrieNode findNodeIndex(TrieNode currentNode, int i){
| > // if(currentNode.index == i) return currentNode;
| > if(currentNode.link != null) findNodeIndex(currentNode.link, i);
| > //System.out.println( currentNode);
| > if(currentNode.index == i) return currentNode;
| > if(currentNode.next != null) findNodeIndex(currentNode.next, i);
| > //if(currentNode.index == i) return currentNode;
| > return null;
| >
| > }
| >
| > I have tried putting the test in various places without success, any
| > ideas why this fails?
| >
| > If it helps i put Trie.java herehttp://pastebin.ca/721376
| >
| > and the test file, trietest.java herehttp://pastebin.ca/721378
| >
| > any help is appreciated
| > Chuck
|
| Hi Chuck,
|
| You are returning from findNodeIndex too early. I have posted the
| corrected findNodeIndex here:
|
| http://pastebin.ca/721497
|
| Also, in English, it is spelled "Tree", not "Trie" ;-)

There is a data structure called a "trie"
http://en.wikipedia.org/wiki/Trie.

Matt Humphrey http://www.iviz.com/
 
B

Behrang

Jeez! I have studied CS for more than 6 years and this is the first
time I have seen this term :))
 
J

Joshua Cranmer

Behrang said:
Jeez! I have studied CS for more than 6 years and this is the first
time I have seen this term :))

Tries are discussed in Knuth's The Art of Computer Programming (volume
1, I think). The only major usage I have ever heard of them was in TeX's
hyphenation algorithm. It is, to say the least, not a very popular data
structure.
 
M

Matt Humphrey

| Behrang wrote:
| > Jeez! I have studied CS for more than 6 years and this is the first
| > time I have seen this term :))
|
| Tries are discussed in Knuth's The Art of Computer Programming (volume
| 1, I think). The only major usage I have ever heard of them was in TeX's
| hyphenation algorithm. It is, to say the least, not a very popular data
| structure.

I thought they were used just for dictionaries. When I learned how to do
them (long ago) one of their advantages was that they could be traversed
while in an dense binary format--instead of storing keys and offsets only
certain bit counts are stored. Wikipedia says they're part of the fastest
technique for sorting strings.

Matt Humphrey http://www.iviz.com/
 
J

Joshua Cranmer

Matt said:
| Behrang wrote:
| > Jeez! I have studied CS for more than 6 years and this is the first
| > time I have seen this term :))
|
| Tries are discussed in Knuth's The Art of Computer Programming (volume
| 1, I think). The only major usage I have ever heard of them was in TeX's
| hyphenation algorithm. It is, to say the least, not a very popular data
| structure.

I thought they were used just for dictionaries. When I learned how to do
them (long ago) one of their advantages was that they could be traversed
while in an dense binary format--instead of storing keys and offsets only
certain bit counts are stored. Wikipedia says they're part of the fastest
technique for sorting strings.

s/very popular/well-known/

I too have known some semantics for a while, but I didn't know them
under the name `trie'.
 
C

Christian

Joshua said:
Tries are discussed in Knuth's The Art of Computer Programming (volume
1, I think). The only major usage I have ever heard of them was in TeX's
hyphenation algorithm. It is, to say the least, not a very popular data
structure.
your os probably uses these tries to index your disc storage for faster
searching.. (suffixtrees are also tries)

Also some state of the art p2p systems use a distributed trie instead of
a normal dht.
 
C

chuck

| You are returning from findNodeIndex too early. I have posted the
| corrected findNodeIndex here:
|
| http://pastebin.ca/721497
|
| Also, in English, it is spelled "Tree", not "Trie" ;-)

There is a data structure called a "trie"
http://en.wikipedia.org/wiki/Trie.

Matt Humphrey http://www.iviz.com/


Thanks Behrang.

Yes, I too thought Trie was a misprint, however it is a real data
structure. In my case, I am using a trie for Lempel-Ziv
encoding/decoding.

Chuck
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top