Что такое префиксное дерево (trie) и когда оно полезно?

Question

Accepted Answer

**Префиксное дерево** (trie) — это дерево, где каждое **ребро** представляет символ, а каждый **путь от корня** образует префикс. Слова с общим префиксом используют один и тот же путь, что делает поиск по префиксу чрезвычайно быстрым.

## Структура

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

## Код

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

## Сложность

| Операция | Время |
|---|---|
| вставка | O(L) |
| поиск | O(L) |
| запрос по префиксу | O(L) |

Критически важно, что стоимость зависит от **длины слова L**, а *не* от количества сохранённых слов.

## Компромиссы

- **Преимущества:** быстрый поиск по префиксу; автодополнение; общие префиксы экономят место для похожих слов.
- **Недостатки:** высокие накладные расходы памяти на узел (карта потомков для каждого); может использовать больше памяти, чем hash set для несвязанных ключей.

## Почему это важно

Традиционные деревья работают в автодополнении, проверке орфографии, таблицах маршрутизации IP и в поиске на основе словаря, где важно **сопоставление префиксов**.

Тогда как hash set отвечает только на вопрос «точное совпадение?», префиксное дерево дополнительно эффективно отвечает на «какие слова начинаются с X?»

Операция	Время
вставка	O(L)
поиск	O(L)
запрос по префиксу	O(L)