Trie (prefixový strom)

O(L) per word

Trie (prefixový strom) je strom, kde je každá hrana označená znakem a cesta od kořene vyhláskuje prefix. Slova, která začínají stejně, sdílejí stejné uzly — "car", "card" a "cat" sdílejí cestu "ca" — a uzel je označený (tady zeleným kroužkem), když na něm končí celé slovo. Vložení i hledání slova jen sestoupí po jednom znaku, takže stojí O(L) pro slovo délky L, ať je uloženo slov kolik chce. Daní je paměť, protože každý odlišný prefix dostane vlastní uzly. Trie pohání automatické doplňování, kontrolu pravopisu, směrování IP i slovníkové vyhledávání. Hledání skončí jedním ze tří způsobů: slovo je nalezeno (končí na označeném uzlu), je jen prefixem uložených slov (cesta existuje, bez označení), nebo chybí (cesta se přeruší).

Prefixový strom
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Pro vložení slova začni v kořeni a sleduj jednu hranu na znak.
  2. Pokud hrana pro znak ještě neexistuje, vytvoř uzel.
  3. Označ poslední uzel jako konec slova (zelený kroužek).
  4. Při hledání projdi znaky — nalezeno jen když všechny existují a poslední uzel je označený.

Pseudokód

1trie:                               # O(L) per word2  insert(word):3    start at the root4    for each char: follow the child edge, or create it5    mark the final node as end-of-word6  search(word):7    walk the chars from the root8    found if every char exists AND the last node is end-of-word