Kas yra trie (priešdėlio medis) ir kada jis naudingas?

Question

Accepted Answer

**Trie** (priešdėlio medis) yra medis, kuriame kiekvienas **briauna** reiškia simbolį ir kiekvienas **kelias nuo šaknies** sudaro priešdėlį. Žodžiai, kurie dalijasi priešdėliu, dalijasi tuo pačiu keliu, todėl priešdėlio paieška yra itin greita.

## Struktūra

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## Kodas

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = word length
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## Sudėtingumas

| Operacija | Laikas |
|---|---|
| įterpimas | O(L) |
| paieška | O(L) |
| priešdėlio užklausa | O(L) |

Svarbu tai, kad kaina priklauso nuo **žodžio ilgio L**, *o ne* nuo saugomų žodžių skaičiaus.

## Kompromisai

- **Pranašumai:** greita priešdėlio paieška; automatinis užbaigimas; bendrinti priešdėliai sutaupo vietą panašiems žodžiams.
- **Trūkumai:** didelis atminties režimas kiekvienai mazgui (kiekviename—žodžio žemėlapis); gali naudoti daugiau vietos nei hash rinkinys nesusijusiems raktams.

## Kodėl tai svarbu

Trie naudojami automatiniame užbaigime, rašybos tikrintuvuose, IP maršrutizavimo lentelėse ir žodyno paieškoje, kur svarbus **priešdėlio** atitikimas.

Kai hash rinkinys atsakinėja tik į "tikslus atitikimas", trie papildomai efektyviai atsakinėja į "kokie žodžiai prasideda X?"