5.1. Concept
This section gives an overview of tries.
Last updated
Was this helpful?
This section gives an overview of tries.
Last updated
Was this helpful?
A trie is a tree where each node has:
0-to-many children,
A key whose type is character,
A value that can be any type of object, and
An end-state that indicates if the node and its ancestors together represent the end of a certain word.
Let us consider the following list of strings:
Given the strings as keys, a binary search tree can be constructed as follows using a balancing algorithm:
How many character comparisons does it need to make to search a string in a balanced BST?
With the same list of strings, a trie can be constructed as follows:
1st cell: key (a character).
2nd cell: value (the index of the string that the node represents).
3rd cell: end-state (T for true, F for false).
What is the worst-case complexity of searching a string in a trie?
