Trie (префиксное дерево) — древовидная структура для хранения строк, где каждый узел представляет символ. Путь от корня до узла — префикс. Поиск строки длины m за O(m) вне зависимости от количества строк. Идеален для автодополнения, спелл-чекера, IP-маршрутизации (Patricia trie). В Go реализуется через struct с map[rune]*TrieNode. Недостаток — потребляет больше памяти, чем хеш-таблица. На практике для большинства задач map[string] достаточно, но trie незаменим для prefix-операций.

Что такое trie?