Skip to content

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 ​

SintaxisDescripción
Trie()Crea un nuevo árbol de prefijo vacío

Métodos ​

MétodoFirmaDevuelveDescripción
insert(word: string) => voidvoidInserta una copia de word; las inserciones duplicadas se ignoran
search(word: string) => booleanbooleanSi word está almacenada como una palabra completa
startsWith(prefix: string) => booleanbooleanSi alguna palabra almacenada tiene el prefijo dado
len() => usizeusizeNúmero de palabras distintas almacenadas
isEmpty() => booleanbooleanSi el árbol no almacena palabras
clear() => voidvoidElimina todas las palabras

Complejidad ​

OperaciónComplejidad Temporal
insertO(m), longitud de la palabra
searchO(m), longitud de la palabra
startsWithO(m), longitud del prefijo
lenO(1)
isEmptyO(1)
clearO(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());  // 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