Kaj je trie (drevo s predponami) in kdaj je koristno?

Question

Accepted Answer

**Trie** (drevo s predponami) je drevo, kjer vsaka **grana** predstavlja znak in vsaka **pot od korena** tvori predpono. Besede, ki si delijo predpono, si delijo isto pot, kar omogoča izjemno hitro iskanje po predponah.

## Struktura

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

## Koda

```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
```

## Kompleksnost

| Operacija | Čas |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Odločilno je, da je cena odvisna od **dolžine besede L**, *ne* od števila shranjenih besed.

## Kompromisi

- **Prednosti:** hitro iskanje po predponah; samodopopolnjevanje; skupne predpone prihranijo prostor za podobne besede.
- **Slabosti:** visok porabljan pomnilnik na vozlišče (preslikava otrok za vsako vozlišče); lahko porabi več prostora kot hash set za nepovezane ključe.

## Zakaj je to pomembno

Trie-i omogočajo samodopopolnjevanje, preverjanje črkovanja, usmerjevalne tabele IP in iskanje na osnovi slovarja, kjer je **ujemanje predpon** odločilno.

Medtem ko hash set odgovori samo na "točno ujemanje", trie dodatno učinkovito odgovori na "katere besede se začnejo z X?".