Tweet
Trie Tree: find 1,000,000 strings in 0.3 seconds
A Trie as a tree structure that's as fast as a hash.
So, you get the benefits of a tree and a hash.
- blazing fast search
- traverse in Key order
A Trie is the fastest structure for a "prefix’ search.
Anyone interested in adding "IntelliSense" like search to a PB editor, here you go.
The reason a Trie is so fast, each character in the key word is the index to the child node of the next character in the key word.
Instead of doing a string comparison, you’re doing a branch jump based on the ASC() of each character in the key word.
As you move through each character in the key, you’re moving down the tree.
That’s also the reason it’s so good for prefix search, once you reach the end of the prefix in the tree, every key word below there belongs to the prefix. No further comparisons necessary.
A Trie as a tree structure that's as fast as a hash.
So, you get the benefits of a tree and a hash.
- blazing fast search
- traverse in Key order
A Trie is the fastest structure for a "prefix’ search.
Anyone interested in adding "IntelliSense" like search to a PB editor, here you go.
The reason a Trie is so fast, each character in the key word is the index to the child node of the next character in the key word.
Instead of doing a string comparison, you’re doing a branch jump based on the ASC() of each character in the key word.
As you move through each character in the key, you’re moving down the tree.
That’s also the reason it’s so good for prefix search, once you reach the end of the prefix in the tree, every key word below there belongs to the prefix. No further comparisons necessary.
Comment