Java Reference
In-Depth Information
d
g
c
h
a
e
o
o
n
h
u
c
a
t
i
e
l
r
o
$
s
e
c
r
k
t
d
s
e
a
e
k
$
$
$
f
l
t
o
p
e
i
s
$
$
e
n
r
e
h
$
$
$
$
(a)
a
c
d
g
h
n
e
o
u
chicken
horse
a
t
l
o
deer
duck
$
e
goat
goldfish
goose
a
ant
l
anteater
antelope
(b)
Figure13.2
Two variations on the alphabet trie representation for a set of ten
words. (a) Each node contains a set of links corresponding to single letters, and
each letter in the set of words has a corresponding link. “$” is used to indicate
the end of a word. Internal nodes direct the search and also spell out the word
one letter per link. The word need not be stored explicitly. “$” is needed to
recognize the existence of words that are prefixes to other words, such as 'ant' in
this example. (b) Here the trie extends only far enough to discriminate between the
words. Leaf nodes of the trie each store a complete word; internal nodes merely
direct the search.
