help with my recursive trie search

Discussion in 'Java' started by chuck, Oct 1, 2007.

  1. chuck

    chuck Guest

    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
     
    chuck, Oct 1, 2007
    #1
    1. Advertising

  2. chuck

    Behrang Guest

    On Oct 1, 4:15 pm, chuck <> wrote:
    > 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
     
    Behrang, Oct 1, 2007
    #2
    1. Advertising

  3. "Behrang" <> wrote in message
    news:...
    | On Oct 1, 4:15 pm, chuck <> wrote:
    | > 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/
     
    Matt Humphrey, Oct 1, 2007
    #3
  4. chuck

    Behrang Guest

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

    Matt Humphrey wrote:
    > "Behrang" <> wrote in message
    > news:...
    > | On Oct 1, 4:15 pm, chuck <> wrote:
    > | > 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/
     
    Behrang, Oct 1, 2007
    #4
  5. 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.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
     
    Joshua Cranmer, Oct 1, 2007
    #5
  6. "Joshua Cranmer" <> wrote in message
    news:DhdMi.3545$Hb2.3424@trndny07...
    | 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/
     
    Matt Humphrey, Oct 1, 2007
    #6
  7. Matt Humphrey wrote:
    > "Joshua Cranmer" <> wrote in message
    > news:DhdMi.3545$Hb2.3424@trndny07...
    > | 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'.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
     
    Joshua Cranmer, Oct 1, 2007
    #7
  8. chuck

    Christian Guest

    Joshua Cranmer schrieb:
    > 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.
    >

    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.
     
    Christian, Oct 1, 2007
    #8
  9. chuck

    chuck Guest

    >
    > | 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
     
    chuck, Oct 1, 2007
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joseph

    compressed suffix trie

    Joseph, Sep 22, 2004, in forum: Java
    Replies:
    1
    Views:
    547
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=
    Sep 22, 2004
  2. Joseph

    compressed suffix trie

    Joseph, Sep 22, 2004, in forum: C++
    Replies:
    3
    Views:
    1,822
    Victor Bazarov
    Sep 22, 2004
  3. Miki Tebeka

    [ANN] Trie for Python

    Miki Tebeka, Oct 1, 2003, in forum: Python
    Replies:
    0
    Views:
    434
    Miki Tebeka
    Oct 1, 2003
  4. Justin To

    Trie search algorithm

    Justin To, Jun 13, 2008, in forum: Ruby
    Replies:
    0
    Views:
    128
    Justin To
    Jun 13, 2008
  5. markspace

    Patricia trie vs binary search.

    markspace, May 25, 2012, in forum: Java
    Replies:
    32
    Views:
    923
Loading...

Share This Page