Tries
Description
Tries, also known as prefix trees, are data structures used for storing strings in a way that allows for efficient prefix-based queries. Each node in a trie represents a single character of the string, and paths from the root to nodes represent sequences of characters. Tries are commonly used in autocomplete systems and dictionary implementations.
C++ Code
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* current = root;
for (char c : word) {
if (current->children.find(c) == current->children.end()) {
current->children[c] = new TrieNode();
}
current = current->children[c];
}
current->isEndOfWord = true;
}
bool search(string word) {
TrieNode* current = root;
for (char c : word) {
if (current->children.find(c) == current->children.end()) {
return false;
}
current = current->children[c];
}
return current != nullptr && current->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* current = root;
for (char c : prefix) {
if (current->children.find(c) == current->children.end()) {
return false;
}
current = current->children[c];
}
return current != nullptr;
}
};
int main() {
Trie trie;
trie.insert("apple");
cout << (trie.search("apple") ? "Found apple" : "Not found apple") << endl;
cout << (trie.search("app") ? "Found app" : "Not found app") << endl;
cout << (trie.startsWith("app") ? "Starts with app" : "Doesn't start with app") << endl;
return 0;
}
Time and Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion | O(L) | O(L) |
| Search | O(L) | O(1) |
| Starts with (Prefix search) | O(L) | O(1) |
Where:
- L: Length of the string (or key) being inserted, searched, or queried.