ALGORITHMS AND DATA STRUCTURES
Tries
Date Published: | |
Last Modified: |
The word trie comes from the word retrieval. A trie is also known as a digital tree, radix tree or prefix tree.
Each node contains the following:
- A value, which can be
null
- An array of pointers to child nodes, where each one may optionally be
null
.
A trie usually has an empty root node (or ""
). This root node contains a list of nodes, one for each character in the alphabet (e.g. 26 entries for English). The characters are mapped to pointers in the array by their index, were A = 0 and Z = 25.
The value is used to indicate whether or not the sequence of letters from the root node to the current node form a valid word (if they don’t, they only exist because there is a larger word which contains these letters).
Complexity
The worst case time to construct a trie is dependent on the product of the longest word \( m \)
, and how many words the trie contains \( n \)
. This is written using Big-O notation as \( \mathcal{O}(mn) \)
. The time it takes for insertion, deletion and searching is dependent on the product of the length of the word you are inserting, deleting or searching for \( a \)
, and the total number of words \( n \)
. This is expressed as \( \mathcal{O}(an) \)
.
Uses
Tries are used in the following ways:
- Search engines
- Spell-checkers
- Auto-complete
Related Content:
- July 2017 Updates
- Sorting Algorithms
- Python Classes And Object Orientated Design
- Parsing Command-Line Arguments In Python
- Python Sets