Co je to trie (strom s předponami) a kdy je užitečné?

Question

Accepted Answer

**Trie** (strom s předponami) je strom, kde každá **hrana** představuje znak a každá **cesta z kořene** tvoří předponu. Slova, která sdílí předponu, sdílí stejnou cestu, což činí vyhledávání prefixů velmi rychlým.

## Struktura

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

## Kód

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

## Složitost

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

Stěžejně, cena závisí na **délce slova L**, ne na počtu uložených slov.

## Kompromisy

- **Silné stránky:** rychlé vyhledávání prefixů; automatické doplňování; sdílené předpony šetří místo pro podobná slova.
- **Slabé stránky:** vysoká režie paměti na uzel (mapa potomků pro každý); může využít více místa než hash set pro nesouvisející klíče.

## Proč je to důležité

Tries poháňí automatické doplňování, kontrolu pravopisu, tabulky směrování IP a vyhledávání na základě slovníku, kde záleží na porovnávání **prefixů**.

Zatímco hash set odpovídá pouze na "přesná shoda?", trie efektivně odpovídá na "která slova začínají na X?".