Skip to content

Trie ​

Trie implementa uma árvore de prefixo para palavras de string com busca, prefixo, inserção e consulta O(m), onde m é o comprimento da palavra. Ela não é genérica: Trie() cria uma árvore de prefixo vazia que armazena strings de comprimento arbitrário.

Construção ​

SintaxeDescrição
Trie()Cria uma nova árvore de prefixo vazia

Métodos ​

MétodoAssinaturaRetornaDescrição
insert(word: string) => voidvoidInsere uma cópia de word; inserções duplicadas são ignoradas
search(word: string) => booleanbooleanSe word está armazenada como uma palavra completa
startsWith(prefix: string) => booleanbooleanSe alguma palavra armazenada tem o prefixo informado
len() => usizeusizeNúmero de palavras distintas armazenadas
isEmpty() => booleanbooleanSe a árvore não armazena palavras
clear() => voidvoidRemove todas as palavras

Complexidade ​

OperaçãoComplexidade Temporal
insertO(m), comprimento da palavra
searchO(m), comprimento da palavra
startsWithO(m), comprimento do prefixo
lenO(1)
isEmptyO(1)
clearO(n), número de nós armazenados

Exemplos ​

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 e 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