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. 



No comments:

Post a Comment