Trie
Trie implementa un árbol de prefijo para palabras de string con búsqueda, prefijo, inserción y consulta O(m), donde m es la longitud de la palabra. No es genérico: Trie() crea un árbol de prefijo vacío que almacena strings de longitud arbitraria.
Construcción
| Sintaxis | Descripción |
|---|---|
Trie() | Crea un nuevo árbol de prefijo vacío |
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
insert | (word: string) => void | void | Inserta una copia de word; las inserciones duplicadas se ignoran |
search | (word: string) => boolean | boolean | Si word está almacenada como una palabra completa |
startsWith | (prefix: string) => boolean | boolean | Si alguna palabra almacenada tiene el prefijo dado |
len | () => usize | usize | Número de palabras distintas almacenadas |
isEmpty | () => boolean | boolean | Si el árbol no almacena palabras |
clear | () => void | void | Elimina todas las palabras |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
insert | O(m), longitud de la palabra |
search | O(m), longitud de la palabra |
startsWith | O(m), longitud del prefijo |
len | O(1) |
isEmpty | O(1) |
clear | O(n), número de nodos almacenados |
Ejemplos
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