Mikä on trie (etuliitepuu) ja milloin se on hyödyllinen?

Question

Accepted Answer

**Trie** (etuliitepuu) on puu, jossa jokainen **kaari** edustaa merkkiä ja jokainen **polku juuresta** muodostaa etuliitteen. Sanat, jotka jakavat etuliitteen, jakavat saman polun, mikä tekee etuliitehakusta erittäin nopeaa.

## Rakenne

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

## Koodi

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

## Monimutkaisuus

| Operaatio | Aika |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Ratkaisevasti kustannus riippuu **sanan pituudesta L**, ei tallennettujen sanojen määrästä.

## Kompromissit

- **Vahvuudet:** nopea etuliitehaku; automaattinen täydennys; jaetut etuliitteet säästävät tilaa samankaltaisille sanoille.
- **Heikkoudet:** korkea muistikustannus solmua kohti (lapsien kartta jokaiselle); voi käyttää enemmän tilaa kuin hash set liittymättömille avaimille.

## Miksi se on tärkeää

Triet toimivat automaattisen täydennyksen, oikoluvun, IP-reititystaulukoiden ja sanastopohjaisessa haussa, jossa **etuliitteen** vastaavuus on tärkeää.

Vaikka hash set vastaa vain "täsmällinen vastaavuus?", trie vastaa tehokkaasti "mitkä sanat alkavat X:llä?".