Prefix tree

Prefix trees (tries) can be used to implement data structures like sets and associative arrays, but the most common using is when we need to search a sertain word that starts with prefix. It significantly simplifies finding some words with less efforts on typing. Each node of a prefix tree contains a single character and dictionary with children nodes and their values.

• Insert word

For example, if we have word 'banana', firstly we look if in the children of current node there is letter 'b', if yes - we go deeper and do the same operations with letter 'a'. If not, we add 'b' to the list of children of our current node and then continue adding other children. Our prefix tree support such operations: insertion of the word, compession.

Time complexity of insetring the word into the prefix tree is O(n), where n is the length of the word, that we want to insert.

• Building:

Firstly, we built prefix tree based on the insertion of each word in the tree. The first current node of each prefix tree is always an empty string. Each node can pottentially have number of children equivalent to number of letters in alphabet (so it`s 26 for English alphabet and 33 for Ukrainian).

That`s how the prefix tree for the phrase "Hello world!" will look like (the orange nodes represents the end of the words).

The time complexity of buidling a tree will be proporional to sum of length of all words from which we are building a tree.

• Compression:

When we want to compress our prefix tree, we look for nodes that have only one child and connect them into one node. With this algorithm, our tree becomes much more smaller, but if we want to find something, it becomes harder. So we use it only to store tree with less memory capacity, but not to find words.