Data Structures Tries
Tries
A kind of search tree used to store a dynamic set or associative array.
Tries, also known as prefix trees, are a tree-like data structure that allow for efficient lookup times for strings. They manage strings by storing them character-by-character.
Trie operations include insertion, search, and deletion of words. These operations allow tries to efficiently manage words or other character sequences, supporting quick lookups, and prefix searches:
| Operations | Time | Space |
|---|---|---|
| Insert | O(n) | O(n*Σ) |
| Search | O(n) | O(1) |
| StartsWith | O(n) | O(1) |
| Delete | O(n) | O(1) |
Tries are used to store strings or words, the symbol Σ (Sigma) represents the size of the alphabet being used. Essentially, it tells us how many different characters can appear in the strings that the Trie is capable of storing.
Each node in a trie represents a single character from a string and has references to child nodes for consecutive characters (stored in a hashmap). A trie node also has a flag to indicate the end of a word. This structure saves space and speeds up searches:
Inserting a word into a trie means creating a new path of nodes for each character in the word, if that path does not already exist. Starting from the root, for each character, move to the next child node or create a new child node if one doesn't exist, then mark the final node as the end of a word.
Searching for a word in a trie checks each character of the word against the nodes, starting from the root. If at any point the child node does not exist, or if the end of the word is reached without matching the end flag in the node, the search returns false; otherwise, it returns true:
Finding prefixes in a trie is similar to searching for a whole word but we stop at the end of the prefix. If we can follow the characters of the prefix to a node successfully, then the prefix exists in the trie:
Implementing a trie involves defining a trie node class with a children map (to store references to child nodes) and a boolean flag to mark the end of a word. The trie itself is represented by the root node, where all words are accessible by traversing down child nodes corresponding to each character in the word.
Tries efficiently store and search words or sequences of strings. They are useful for tasks involving prefixes, such as autocomplete systems or spell checkers. To get the most out of tries in coding interviews, here are some essential tips and tricks: