Results 1 to 6 of 6

Thread: TRIE problem

  1. #1
    wildheart is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default TRIE problem

    Node InsertNode(string name, Node root)
    {
    int index = 1;
    string key;
    Node currentNode = root;
    while (index <= name.Length)
    {
    key = name[index - 1].ToString();
    Node resultNode = currentNode.Children.GetNodeByKey(key);
    if (resultNode == null)
    {
    Node newNode = new Node(key, name.Substring(0, index));
    if (index == name.Length)
    newNode.IsTerminal = true;
    currentNode.Children.Add(newNode);
    currentNode = newNode;
    }
    else
    {
    currentNode = resultNode;
    }
    index++;
    }
    return root;
    }


    is there anything like this for arrays? i dont no what node is. am guessing its some sort of structure. like a stack or que? i remember reading about linked lists. they have left and right nodes. is that it? can someone show me a similar code using arrays or lists? T-T ya linked lists would be great. i'd get to see the left and right thingi in action. sorry for calling it a thingy. method mayb? i dont no how this insert thing is done :s

    thanx.

  2. #2
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    A node is a general element used to build data structures such as trees, lists, etc.

    A trie is a type of tree structure where the key values dictate the position of a node. The insert methods needs to walk the tree by following the key string so it can find the correct place to insert the node. The nearest array equivalent would be be a hash table, but the two are rather different. Trie - Wikipedia, the free encyclopedia

    An insert method for a linked list:

    Java Code:
    class LinkedListNode {
        private LinkedListNode next;
        private Object data;
    
        public void insertAfter(Object data) {
            LinkedListNode newNode = new LinkedListNode();
            newNode.data = data;
            newNode.next = next;
            this.next = newNode;
        }
    }
    Last edited by OrangeDog; 04-21-2009 at 06:20 PM.
    Don't forget to mark threads as [SOLVED] and give reps to helpful posts.
    How To Ask Questions The Smart Way

  3. #3
    wildheart is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    aah my friend, it is good to see u again. btw, i finished that program. am kinda proud of myself cuz thts one less prg on the shelf to finish. and am even using it. it really did turn out to be convinient though i still have more hopes for it.

    EDIT: ok took me a while to figure out ur code is that of linkedlist. but its not for the TRIE specifically. the code i found, how do i turn it to one that uses linkedlists?


    class LinkedListNode {
    private LinkedListNode next;
    private String newword;

    node InsertNode(String letter, node newroot)
    {
    int index = 1;
    string key;
    LinkedLlistNode newNode = newroot;
    while (index <= newword.Length)
    {
    key = newword[index - 1].ToString();
    LinkedListNode currentNode = newNode.next.newword(key); /* i no am supposed to pass the new key tht refers me to the next node in my TRIE tree for this new word but i dont no what the method is */

    if (newNode == null)
    {
    LinkedListNode childnode = new LinkedListNode(key, newword.Substring(0, index));
    if (index == newword.Length)
    childNode.IsTerminal = true; <= ok i dont no how this can be made using linkedlists. do i say newNode.next = null?
    currentNode.Children.Add(newNode);
    currentNode = newNode;
    }
    else
    {
    newNode= currentNode;
    }
    index++;
    }
    return newroot;
    }
    Last edited by wildheart; 04-21-2009 at 08:31 PM.

  4. #4
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    You can't build a trie using linked lists. Both a trie and a linked list are types of data structure. Tries are typically used for associative maps and linked lists for queues or stacks. You can't build one out of the other. Just like you can't build orange juice out of milk.

    You need to understand how the data structures themselves work before you start trying to implement them in a programming language.
    Don't forget to mark threads as [SOLVED] and give reps to helpful posts.
    How To Ask Questions The Smart Way

  5. #5
    wildheart is offline Member
    Join Date
    Apr 2009
    Posts
    12
    Rep Power
    0

    Default

    i think thts exactly what am trying to find out. how does the code work basically. nywyz thnx for ur help. u really did.

  6. #6
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    It is simultaneously stepping through the characters of the String key and the nodes of the tree from the root node, until it finds the correct position for the new node. See that wikipedia article for a picture.
    Don't forget to mark threads as [SOLVED] and give reps to helpful posts.
    How To Ask Questions The Smart Way

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •