Trie — это структура данных для хранения строк, где каждый узел соответствует символу, а путь от корня образует префикс. Главное преимущество — быстрый поиск по словам и префиксам без полного перебора коллекции.
Где применяют Trie 👇
Автодополнение
Используется в поиске, IDE, мессенджерах и формах ввода. По первым символам можно быстро получить все подходящие слова.Проверка словарей
Подходит для орфографических сервисов, антиспама, фильтрации запрещённых слов и поиска по словарям.Поиск по префиксу
Если нужен ответ на запросы вроде: “все строки, начинающиеся с `api`”, Trie работает особенно эффективно.Маршрутизация и URL matching
Подходит для хранения путей, доменов, команд CLI и шаблонов маршрутов.IP-адреса и сетевые задачи
Специализированные варианты Trie используют для поиска по префиксам в таблицах маршрутизации. 🌐
Почему Trie полезен
Поиск слова: O(L)
Вставка слова: O(L)
Проверка префикса: O(L)
Где L — длина строки. Это лучше, чем многократно сравнивать строки в списке, особенно на больших объёмах данных.
Как устроен Trie 🧩
Каждый узел обычно хранит:
- набор дочерних узлов
- флаг окончания слова (`is_end`)
Пример: слова `cat`, `car`, `care` будут иметь общий путь `c → a`, а дальше разветвляться.
Простая реализация на Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
Минусы Trie ⚠️
- Потребляет больше памяти, чем список или set
- Становится тяжёлым при большом алфавите
- Для коротких наборов слов может быть избыточным
Как оптимизируют
- используют сжатый Trie / Radix Tree
- хранят массивы вместо dict, если алфавит фиксирован
- комбинируют с частотами слов для ранжирования автоподсказок
Когда выбирать Trie
Trie стоит использовать, если:
- много строк
- часто нужен поиск по префиксу
- важна скорость автодополнения
- данные имеют общие начала слов 🚀
Если нужен только точный поиск без префиксов, hash set часто проще и экономнее по памяти.
Подборка каналов про IT — хороший способ следить за архитектурой, алгоритмами, backend, frontend и практикой разработки 📚