Tries¶
A Trie trades memory for prefix work. Each edge consumes one character, so lookup time depends on key length rather than the number of stored words.
Ownership model¶
flowchart LR
accTitle: Shared prefix ownership in a Trie
accDescr: Cat and car share root, c, and a nodes, then branch to t and r terminal nodes. The terminal flag distinguishes a complete word from a prefix.
R["root"] --> C["c"]
C --> A["a"]
A --> T["t · terminal"]
A --> RR["r · terminal"]Invariant: following the characters of a stored word reaches exactly one path, and only a terminal flag marks a complete word.
Tested template¶
@dataclass
class _TrieNode:
children: dict[str, _TrieNode] = field(default_factory=dict)
terminal: bool = False
class Trie:
"""Store strings by shared prefixes."""
def __init__(self) -> None:
self.root = _TrieNode()
def insert(self, word: str) -> None:
node = self.root
for character in word:
# Create only the missing suffix; existing prefixes are shared.
node = node.children.setdefault(character, _TrieNode())
node.terminal = True
def contains(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.terminal
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def _walk(self, text: str) -> _TrieNode | None:
node = self.root
for character in text:
node = node.children.get(character)
if node is None:
return None
return node
class Trie {
public:
Trie() : nodes_(1) {}
void insert(const std::string& word) {
int node = 0;
for (const char character : word) {
const auto found = nodes_[node].children.find(character);
if (found == nodes_[node].children.end()) {
// Create only the missing suffix; existing prefixes are shared.
const int child = static_cast<int>(nodes_.size());
nodes_[node].children[character] = child;
nodes_.push_back(Node());
node = child;
} else {
node = found->second;
}
}
nodes_[node].terminal = true;
}
bool contains(const std::string& word) const {
const int node = walk(word);
return node >= 0 && nodes_[node].terminal;
}
bool starts_with(const std::string& prefix) const {
return walk(prefix) >= 0;
}
private:
struct Node {
std::unordered_map<char, int> children;
bool terminal = false;
};
int walk(const std::string& text) const {
int node = 0;
for (const char character : text) {
const auto found = nodes_[node].children.find(character);
if (found == nodes_[node].children.end()) {
return -1;
}
node = found->second;
}
return node;
}
std::vector<Node> nodes_;
};
class Trie {
public:
Trie() : nodes_(1) {}
void insert(const std::string& word) {
int node = 0;
for (const char character : word) {
const auto found = nodes_[node].children.find(character);
if (found == nodes_[node].children.end()) {
// Create only the missing suffix; existing prefixes are shared.
const int child = static_cast<int>(nodes_.size());
nodes_[node].children[character] = child;
nodes_.push_back(Node());
node = child;
} else {
node = found->second;
}
}
nodes_[node].terminal = true;
}
bool contains(const std::string& word) const {
const int node = walk(word);
return node >= 0 && nodes_[node].terminal;
}
bool starts_with(const std::string& prefix) const {
return walk(prefix) >= 0;
}
private:
struct Node {
std::unordered_map<char, int> children;
bool terminal = false;
};
int walk(const std::string& text) const {
int node = 0;
for (const char character : text) {
const auto found = nodes_[node].children.find(character);
if (found == nodes_[node].children.end()) {
return -1;
}
node = found->second;
}
return node;
}
std::vector<Node> nodes_;
};
Insert and lookup take O(length) time. Space is proportional to created
prefix nodes; dense alphabets may need compressed edges or sparse maps.
Extensions¶
- Store a count at each node for prefix-frequency queries.
- Store top suggestions for autocomplete.
- Add failure links to form Aho–Corasick for many patterns in one text.
- Use a bitwise Trie for maximum-XOR queries over integers.