From: "nicholasmabry@..." Date: 2008-06-11T08:34:59+09:00 Subject: Re: Trie data structure On Jun 10, 5:44 pm, Justin To wrote: > I'm trying to implement a trie data structure for my parsing program > that parses numbers....I'm lost as to what the algorithm would look > like. Also, I don't fully understand the wikipedia definition athttp://en.wikipedia.org/wiki/Triewhen it says "...no node in the tree > stores the key associated with that node; instead, its position in the > tree shows what key it is associated with..." > > Any help is appreciated! > -- > Posted viahttp://www.ruby-forum.com/. The basic idea is that each node contains only a partial key, the final piece of its full key. So if the node you're adding should have the full key "hi": - It will contain the partial key "i". - Its parent will have the partial key "h". - Its grandparent will have an empty partial key - the root node. As the lookup algorithm example on the wiki page describes, looking up a value by key is a matter of starting at the root node and following each path that leads you to the next item in the full key. This differs from a binary tree in that the tree structure is not only a means to locate the key, but a reflection of the key itself. Have fun!