trie = a data structure used to store large sets of strings

while storing in an array etc. is ok (O(n) lookup), we can use a trie to improve to O(L) where L is the length of the string

• example conceptualisations of tries

each word is essentially stored as a linked-list of letters, where we mark where each word terminates (e.g. allows us to store both ‘app’ and ‘apple’)

each node in a trie contains:

• one part of a key (one character usually) — store the character
• pointers to children (up to ALPHABET_LEN = 26 usually) — point to subsequent letters
• a ‘finished’ flag — mark the end of a word
• (optionally) additional data (e.g. word frequency)
• possible node structure in C

depth of a trie = length of longest word

major disadvantage of tries: tries take up a lot of space

pointers to children nodes for each letter could be 8 bytes per pointer

each node will need even more children to store characters such as uppercase letters or numeric characters etc.

trie implementation

• trie insertion
• trie deletion

performance analysis

space complexity = O(n)

n = sum of lengths of all strings

insertion complexity = O(L)

L = length of word to insert

search complexity = O(L)

L = length of word to search

alternatives to normal tries

1. BST-like tries

   to reduce the space problem that tries face, we can implement them more like BSTs

   each node has two children — down and right

   going down gives the next letter

   going right gives alternate letters

   • example BST-like trie

   less space used, maintaining (insert / delete) not really affected

   however, this will take more time to search