[Tema dana: prefiksno stablo iliti STOBLO.]
Prije tjedan dana, na 2. izbornom ispitu pojavio se zadatak sa stablom prefiksa, koje služi da bismo efikasno… Ma skužit ćete iz zadataka.
Ponekad se na crtežu ove strukture slova zapisuju u vrhove stabla. To je pogrešno: slova su bridovi, a ne vrhovi stobla. Vrh nije slovo nego prefiks, tj. niz slova kojima smo došli do tog vrha. Što se tiče implementacije, gledajući rješenja s izbornog ispita, vidio sam da neki koriste pointere, a neki ono što i ja koristim: običnu cjelobrojnu tablicu dimenzija N x 26, gdje je N maksimalan broj vrhova stabla, u kojoj sljedbenik[X][slovo] = Y znači da nakon vrha broj X slijedi slovo kojim dolazimo do vrha broj Y. Ako je ta vrijednost 0 (default), znači da nema tog slova nakon prefiksa X. Dodavanje novog vrha svodi se na operaciju sljedbenik[X][slovo] = broj_vrhova++.
Engleski je trie, a etimologija je zanimljiva (s Wikipedije):
Tries were first described by René de la Briandais in 1959. The term trie was coined by Edward Fredkin, who pronounces it /ˈtriː/ (as “tree”), after the middle syllable of retrieval. However, other authors pronounce it /ˈtraɪ/ (as “try”), in an attempt to distinguish it verbally from “tree”.
E sad, u Lijepoj Našoj netko (možda Luka Kalinovčić ili netko prije njega) počeo je ovu strukturu zvati stoblom (logika je jasna: tree –> trie, stablo –> stoblo). Taj pojam i dalje koristimo kolokvijalno. Kraće je reći stoblo nego prefiksno stablo ili stablo prefiksa. Ali nemojte ga baš tako zvati u diplomskom radu, čudno će vas gledati.
Evo jos jedan zadatak:
https://codeforces.com/contest/706/problem/D
Sviđa mi seSviđa mi se