Trie
-
conceived by Ed Fredkin (professor at Carnegie Mellon) in ???
-
tree that stores one part of an element per node
-
usually element is stored in a node (1:1)
-
chains of parts can be reused
-
all chain endings are marked: C-A-R-P-E-T
-
-
used for dictionaries, prediction and autocompletes (mobile especially)
-
possible operations: adding/inserting and querying/finding
-
used in ???.
Important
|
Great, because
Is very memory efficient, has lots of variants and … |