From Wikipedia, the free encyclopedia
In computer science, a trie [L1 ], 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:
NEM 2008-06-09: Here's a very simplistic trie implementation based on straight-forward use of nested dicts (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 {}
}
# 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 {
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"
}