source: cs50
Wednesday, March 10, 2021
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.
Subscribe to:
Posts (Atom)