Over the last two weeks I wrote about how to construct and query a string prefix-trie. We used the data structure to quickly find all strings with a given prefix, and to find the longest common prefix in that list.
Today we will take a look at how we can use arrays to improve performance even further. We will also take a closer look at the run-time of our algorithms from last week’s posts and show how our new approach is significantly better.
While we are looking at the example of a prefix-trie, the same method can be applied to any static tree.