TRIE problem

[wildheart]

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.

[OrangeDog]

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:

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;
    }
}

[wildheart]

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;
}

[OrangeDog]

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.

[wildheart]

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

[OrangeDog]

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.