Czym jest trie (drzewo prefiksów) i kiedy jest przydatne?

Question

Accepted Answer

**Trie** (drzewo prefiksów) to drzewo, w którym każda **krawędź** reprezentuje znak, a każda **ścieżka od korzenia** tworzy prefiks. Słowa, które mają wspólny prefiks, dzielą tę samą ścieżkę, co sprawia, że wyszukiwanie prefiksów jest niezwykle szybkie.

## Struktura

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

## Kod

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

## Złożoność

| Operacja | Czas |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

Krucjalnie, koszt zależy od **długości słowa L**, a *nie* od liczby przechowywanych słów.

## Kompromisy

- **Zalety:** szybkie wyszukiwanie prefiksów; autouzupełnianie; wspólne prefiksy oszczędzają miejsce dla podobnych słów.
- **Wady:** duże obciążenie pamięcią na każdym węźle (mapa dzieci dla każdego węzła); może zajmować więcej miejsca niż hash set dla niezwiązanych ze sobą kluczy.

## Dlaczego to ważne

Trie są podstawą autouzupełniania, sprawdzaczy ortografii, tablic routingu IP i wyszukiwania opartego na słowniku, gdzie istotne jest dopasowanie **prefiksu**.

Gdy hash set udziela odpowiedzi tylko na pytanie "czy istnieje dokładnie to?", trie dodatkowo odpowiada na pytanie "które słowa zaczynają się na X?" w wydajny sposób.