Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 28/32

Trie: the prefix tree

✕
1/7

One letter per step

A trie (pronounced *try*) stores words by spreading their letters across a tree: each node has a Map of children, one for each letter that can come next, and a fin flag that says "a word ends here".

Words that start the same way share a path: "sol", "sopa" and "sopes" go through the same s and the same o, and split later. That's why the trie is the structure behind autocomplete and dictionaries.

leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • Only one letter leaves the root, s: all four words start with it.
  • After the s there are two paths: o (sol, sopa, sopes) and a (salsa).
  • After "so" they split again: l for "sol" and p for "sopa" and "sopes".

Trie (Wikipedia, Spanish) ↗

The whole lesson on one page

One letter per step

A trie (pronounced *try*) stores words by spreading their letters across a tree: each node has a Map of children, one for each letter that can come next, and a fin flag that says "a word ends here".

Words that start the same way share a path: "sol", "sopa" and "sopes" go through the same s and the same o, and split later. That's why the trie is the structure behind autocomplete and dictionaries.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "salsa"]) insertar(raiz, p);

console.log([...raiz.hijos.keys()]);
console.log([...raiz.hijos.get("s").hijos.keys()]);
console.log([...raiz.hijos.get("s").hijos.get("o").hijos.keys()]);
  • Only one letter leaves the root, s: all four words start with it.
  • After the s there are two paths: o (sol, sopa, sopes) and a (salsa).
  • After "so" they split again: l for "sol" and p for "sopa" and "sopes".

Is it a word or just the start of one?

Searching means going down letter by letter. If a child is missing at any point, the word isn't there. If you reach the end, there's still one question: does that node have fin? "sop" exists as a path, but nobody stored "sop" as a word.

What matters is the cost: going down costs O(length of the word). It doesn't matter whether the trie holds four words or a hundred thousand.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

function bajar(raiz, texto) {
  let nodo = raiz;
  for (const letra of texto) {
    nodo = nodo.hijos.get(letra);
    if (!nodo) return null;
  }
  return nodo;
}

const existe = (raiz, p) => { const n = bajar(raiz, p); return n !== null && n.fin; };
const empiezaCon = (raiz, pre) => bajar(raiz, pre) !== null;

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "salsa"]) insertar(raiz, p);

console.log(existe(raiz, "sopa"));
console.log(existe(raiz, "sop"));
console.log(empiezaCon(raiz, "sop"));
console.log(existe(raiz, "taco"));
  • "sopa" is there: the path exists and its last node has fin.
  • "sop" is not a word (false), but it is a prefix (true): the path exists, the flag doesn't.
  • "taco" fails on the first letter: no t leaves the root.

Autocomplete

To suggest words, first go down to the prefix's node, and from there walk everything hanging below it (a depth-first walk), collecting every path that reaches a fin.

The work depends on how many suggestions there are, not on the size of the dictionary: anything that doesn't start with the prefix isn't even touched.

class NodoTrie {
  constructor() {
    this.hijos = new Map();
    this.fin = false;
  }
}

function insertar(raiz, palabra) {
  let nodo = raiz;
  for (const letra of palabra) {
    if (!nodo.hijos.has(letra)) nodo.hijos.set(letra, new NodoTrie());
    nodo = nodo.hijos.get(letra);
  }
  nodo.fin = true;
}

function bajar(raiz, texto) {
  let nodo = raiz;
  for (const letra of texto) {
    nodo = nodo.hijos.get(letra);
    if (!nodo) return null;
  }
  return nodo;
}

function autocompletar(raiz, prefijo) {
  const res = [];
  function juntar(nodo, camino) {
    if (nodo.fin) res.push(camino);
    for (const [letra, hijo] of nodo.hijos) juntar(hijo, camino + letra);
  }
  const nodo = bajar(raiz, prefijo);
  if (nodo) juntar(nodo, prefijo);
  return res;
}

const raiz = new NodoTrie();
for (const p of ["sol", "sopa", "sopes", "sal", "salsa"]) insertar(raiz, p);

console.log(autocompletar(raiz, "sop"));
console.log(autocompletar(raiz, "sal"));
console.log(autocompletar(raiz, "x"));
  • "sop" suggests "sopa" and "sopes".
  • "sal" suggests itself (its node has fin) and then "salsa", which hangs below it.
  • "x" leads to no node: empty array.