From Wikipedia, the free encyclopedia

In computer science, a ''trie'' [http://en.wikipedia.org/wiki/Trie], or ''prefix tree'', is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, 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. All the descendants of any one node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that happen to correspond to keys of interest.

----
[NaviServer] uses a ''trie'' for url dispatching:

   * http://naviserver.cvs.sourceforge.net/naviserver/naviserver/nsd/urlspace.c?view=markup

----
[NEM] 2008-06-09: Here's a very simplistic ''trie'' implementation based on straight-forward use of nested [dict]s
(typically a trie in [C] or [Java] would instead using a fixed-size array and indexing directly based on character (e.g.
restricting words to contain only characters a-z)):
======
#  trie.tcl --
#
#       Simple implementation of tries in Tcl.
#

package require Tcl     8.5
package provide trie    0.1

namespace eval ::trie {
    namespace export {[a-z]*}
    namespace ensemble create

    # create an empty trie
    proc create {} { dict create }
    # add a word to a trie contained in trieVar
    proc add {trieVar word} {
        upvar 1 $trieVar trie
        dict set trie {*}[split $word ""] END 1
    }
    # check if a given word is contained in a trie
    proc contains {trie word} {
        dict exists $trie {*}[split $word ""] END
    }
    # get the sub-trie of all words corresponding to a given prefix
    proc get {trie {prefix ""}} {
        dict get $trie {*}[split $prefix ""]
    }
    # iterate through all words with a given prefix in a trie calling a callback for each one. The
    # callback will be called with the string of each word.
    proc words {trie cmd {prefix ""}} {
        words-helper [get $trie $prefix] $cmd $prefix
    }
    proc words-helper {trie cmd prefix} {
        dict for {k v} $trie {
            if {$k eq "END"} { continue }
            set word $prefix$k
            if {[dict exists $v END]} {
                invoke 1 $cmd $word
            }
            words-helper $v $cmd $word
        }
    }

    # Private helpers
    proc invoke {level cmd args} {
        if {[string is integer -strict $level] && $level >= 0} { incr level }
        uplevel $level $cmd $args
    }
}
======
And a quick test/demo:
======
proc test {} {
    set t [trie create]
    foreach word {howdy hello who where what when why how} { trie add t $word }
    puts "t = $t"
    puts "words:"
    trie words $t puts
    puts "all wh- words:"
    trie words $t puts "wh"
}
======
----
!!!!!!
%| [Category Data Structure] | [Category Glossary] |%
!!!!!!