Skip to content

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 ​

SyntaxDescription
Trie()Create a new empty trie

Methods ​

MethodSignatureReturnsDescription
insert(word: string) => voidvoidInsert a copy of word; duplicate insertions are ignored
search(word: string) => booleanbooleanWhether word is stored as a complete word
startsWith(prefix: string) => booleanbooleanWhether any stored word has the given prefix
len() => usizeusizeNumber of distinct stored words
isEmpty() => booleanbooleanWhether the trie stores no words
clear() => voidvoidRemove all words

Complexity ​

OperationTime Complexity
insertO(m), word length
searchO(m), word length
startsWithO(m), prefix length
lenO(1)
isEmptyO(1)
clearO(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());  // 3
tyrus
const t = Trie();
t.insert("apple");
t.insert("app");

print(t.search("apple"));    // true
print(t.search("app"));      // true
print(t.search("apricot"));  // false

startsWith ​

tyrus
const t = Trie();
t.insert("apple");

print(t.startsWith("app"));  // true
print(t.startsWith("ban"));  // false
print(t.startsWith("apple"));  // true

len and isEmpty ​

tyrus
const t = Trie();

print(t.isEmpty());  // true

t.insert("apple");

print(t.len());      // 1
print(t.isEmpty());  // false

clear ​

tyrus
const t = Trie();
t.insert("apple");

print(t.len());  // 1

t.clear();

print(t.len());      // 0
print(t.isEmpty());  // true