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
| Sintaxe | Descrição |
|---|---|
Trie() | Cria uma nova árvore de prefixo vazia |
Métodos
| Método | Assinatura | Retorna | Descrição |
|---|---|---|---|
insert | (word: string) => void | void | Insere uma cópia de word; inserções duplicadas são ignoradas |
search | (word: string) => boolean | boolean | Se word está armazenada como uma palavra completa |
startsWith | (prefix: string) => boolean | boolean | Se alguma palavra armazenada tem o prefixo informado |
len | () => usize | usize | Número de palavras distintas armazenadas |
isEmpty | () => boolean | boolean | Se a árvore não armazena palavras |
clear | () => void | void | Remove todas as palavras |
Complexidade
| Operação | Complexidade Temporal |
|---|---|
insert | O(m), comprimento da palavra |
search | O(m), comprimento da palavra |
startsWith | O(m), comprimento do prefixo |
len | O(1) |
isEmpty | O(1) |
clear | O(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()); // 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 e 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