🗂 Что такое Префиксное дерево (Trie) и зачем оно нужно? Префиксное дерево, или Trie — это структура данных, которая позволяет хранить и искать строки, организуя их по префиксам. Давайте разберемся, что такое префиксы и как работает Trie. 🔹 Что такое префиксы? Префикс — это начало строки, состоящее из её первых символов. Например, для слова computer префиксами будут: • c, co, com, comp и так далее, вплоть до самого слова computer. Таким образом, префиксы — это части слов, которые постепенно расширяются. Если несколько слов начинаются с одинаковых символов, их префиксы можно хранить общими частями, экономя место и ускоряя поиск. 🔹 Как работает Trie? Trie построен на основе префиксов, поэтому он особенно полезен, когда нужно: 1. Находить слова по их началу (например, для автозаполнения). 2. Проверять, существует ли слово в словаре. 3. Быстро находить все слова с общим префиксом, что часто используется для поиска частот слов или подсчета их количества. В Trie каждый узел представляет один символ, а общие префиксы слов группируются вместе. Например, для слов cat, car и cap: • c будет общим узлом, • a — общим дочерним узлом, • далее t, r, p будут храниться отдельно для каждой ветви. Пример использования Trie на Python: class TrieNode: def __init__(self): self.children = {} # Словарь для хранения дочерних узлов self.is_end_of_word = False # Метка конца слова class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.is_end_of_word = True def search(self, word): node = self.root for char in word: if char not in node.children: return False node = node.children[char] return node.is_end_of_word # Пример использования Trie trie = Trie() trie.insert("car") trie.insert("cat") print(trie.search("car")) # Вывод: True print(trie.search("care")) # Вывод: False 🔸 Как это работает? 1. Добавление слова — при добавлении каждого символа проверяется, есть ли уже такой узел в префиксе. Если нет — он создается. 2. Поиск — начинается с корневого узла и проверяется каждый символ по порядку. Если все символы найдены и последний узел помечен как конец слова, оно существует. Trie отлично подходит для работы с текстом и делает поиск и автозаполнение гораздо быстрее!