Trie
Trie implements a prefix tree for string words with O(m) search, prefix, insertion, and lookup, where m is the length of the word. It is non-generic: Trie() creates an empty trie storing arbitrary-length strings.
Construction
| Syntax | Description |
|---|---|
Trie() | Create a new empty trie |
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
insert | (word: string) => void | void | Insert a copy of word; duplicate insertions are ignored |
search | (word: string) => boolean | boolean | Whether word is stored as a complete word |
startsWith | (prefix: string) => boolean | boolean | Whether any stored word has the given prefix |
len | () => usize | usize | Number of distinct stored words |
isEmpty | () => boolean | boolean | Whether the trie stores no words |
clear | () => void | void | Remove all words |
Complexity
| Operation | Time Complexity |
|---|---|
insert | O(m), word length |
search | O(m), word length |
startsWith | O(m), prefix length |
len | O(1) |
isEmpty | O(1) |
clear | O(n), number of stored nodes |
Examples
insert
tyrus
import { Trie } from "tyrus:algorithm";
const t = Trie();
t.insert("apple");
t.insert("app");
t.insert("banana");
print(t.len()); // 3search
tyrus
const t = Trie();
t.insert("apple");
t.insert("app");
print(t.search("apple")); // true
print(t.search("app")); // true
print(t.search("apricot")); // falsestartsWith
tyrus
const t = Trie();
t.insert("apple");
print(t.startsWith("app")); // true
print(t.startsWith("ban")); // false
print(t.startsWith("apple")); // truelen and isEmpty
tyrus
const t = Trie();
print(t.isEmpty()); // true
t.insert("apple");
print(t.len()); // 1
print(t.isEmpty()); // falseclear
tyrus
const t = Trie();
t.insert("apple");
print(t.len()); // 1
t.clear();
print(t.len()); // 0
print(t.isEmpty()); // true