trie (comes from the word "retrieve") - actually a tree made up of arrays

 

a tree whose nodes are each arrays

and each of those arrays are arrays of pointers to other nodes

constant time lookups and insertions

if someone's name has 200 letters , lookup time would be  big O of (200)

it doesnt matter how many names are in the trie data structure (1 billion, 2 billion, 3 billion), lookup time only depends on number of letters in name

tries give you the holy grail of constant time

source: cs50.