Tries in Swift
Tries are prefix trees, where the key is usually a String.
If you think that sounds something like a use for a dictionary in Swift, well, maybe you should read on and see the evidence.
Prerequisites:
- Dictionaries
- Some experience of trees and terminology (i.e. root, edge, child, parent, node, path etc.)
The basics
A trie is a special case of a tree where characters are stored at each node, and a path down the tree represents a word.
Each node will represent a character of a word, so w->o->r->d would consist of 4 nodes.
When adding words to the trie we do not need to worry about key collisions, and we don’t require a hashing algorithm to give a unique path to elements.
Big O
Inserting a String of length(n) should take O(n)
Checking the trie for a String of length(n) should take O(n)
Removing an element should take O(n)
The classes
We will create two classes. One will be for the nodes (TrieNode) and one will be to store the…
