trie
Főnév
trie (tsz. tries)
- (informatika) Trie (ejtsd: „tráj” vagy „trájfa”) (aka prefix tree) egy speciális fa (tree) adatstruktúra, amelyet főként szövegek, szavak vagy karakterláncok tárolására és gyors keresésére használnak. A trie-t gyakran hívják előtagfának vagy prefixfának, mert az adatok közös előtagjai alapján szervezi az elemeket.
1. Mi az a trie?
A trie egy olyan fastruktúra, ahol minden csomópont egy karaktert vagy jellemzőt tárol, és az útvonal a gyökértől egy levélig egy szó vagy karakterlánc egy előtagját vagy teljes értékét reprezentálja.
2. Felépítés
- Gyökércsomópont: üres karaktert vagy nullát tartalmaz.
- Csomópontok: minden csomópont egy karaktert tárol, és mutatókat tartalmazhat a következő karakterek csomópontjaira.
- Levélcsomópontok: általában jelzik, hogy egy adott karakterlánc (pl. egy szó) véget ér itt.
3. Működés
- Szavakat vagy karakterláncokat úgy tárolunk, hogy az egyes karakterekhez egy-egy csomópont tartozik.
- Közös előtagok esetén a szavak megosztják az első csomópontokat, így hatékonyan tárolható sok adat.
- Keresésnél egy adott szó karaktereit követve haladunk a fán, hogy megtaláljuk, létezik-e az adott szó vagy prefix.
4. Előnyök
- Gyors keresés: a keresés időkomplexitása általában a keresett szó hosszával arányos, nem pedig a teljes adatbázis méretével.
- Prefix alapú keresés: könnyen megvalósíthatók az előtag keresések, automatikus kiegészítés (autocomplete).
- Hatékony memóriahasználat: közös előtagok megosztása miatt.
5. Hátrányok
- Memóriaigény: nagy ábécé esetén sok csomópontot kell tárolni.
- Implementációs komplexitás: bonyolultabb adatstruktúra, mint például egy egyszerű lista vagy hash-tábla.
6. Használati példák
- Szótárak és keresőmotorok (szavak keresése, autókitöltés)
- IP-címek vagy URL-ek tárolása
- DNS névfeloldás
- Szövegfeldolgozó alkalmazások
7. Összefoglalás
A trie egy hatékony adatstruktúra karakterláncok és szavak tárolására és keresésére, amely a közös előtagokat használja ki az adatok rendezésére. Különösen hasznos előtag alapú keresésekhez és olyan alkalmazásokhoz, ahol gyors hozzáférés szükséges nagyszámú szöveges elemhez.