Coding Interview Prep · Урок

Класс TrieNode: вставка и поиск

Создайте TrieNode со словарём дочерних узлов и флагом is_end, реализуйте вставку и точный поиск и проанализируйте время O(m) на операцию, где m — длина слова

«Класс TrieNode: вставка и поиск» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Что такое Trie

Trie (префиксное дерево) — это древовидная структура данных, в которой каждая вершина представляет один символ. Слова хранятся как цепочки символов от корня к листу. Корень представляет пустую строку. Каждый путь от корня к вершине с is_end = True образует сохранённое слово. Trie идеально подходят для запросов по префиксу, например autocomplete, проверки орфографии и маршрутизации IP, превосходя хеш-таблицы в этих случаях.

Проектирование класса TrieNode

У TrieNode есть два поля: children — словарь, сопоставляющий символы дочерним узлам TrieNode, и is_end — логическое значение, показывающее, является ли эта вершина концом сохранённого слова. Использование словаря вместо массива фиксированного размера на 26 символов обобщает структуру для любого набора символов и экономит память в разреженных Trie. Каждая вершина Trie представляет ровно одну позицию символа в словах, расположенных ниже неё.

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False  # True if a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def __repr__(self):
        return f'Trie(root with {len(self.root.children)} children)'

t = Trie()
print(t)  # Trie(root with 0 children)

Операция insert

Чтобы вставить слово, начните с корня и создавайте новый TrieNode для каждого символа, которого ещё нет в children текущей вершины. Обработав все символы, установите для is_end значение «истина» в последней вершине. Вставка 'apple' и 'app' создаёт цепочку a→p→p→l→e (для 'apple' значение is_end в последней вершине равно «истина»); вершина p в позиции 3 также получает значение «истина» для 'app'.

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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)

Операция search

Чтобы найти точное слово, проходите по Trie, следуя за каждым его символом. Если в children текущей вершины отсутствует какой-либо символ, верните значение «ложь». Если все символы найдены, верните node.is_end — значение «истина» только в том случае, если слово заканчивается именно здесь, а не является лишь префиксом. Это различие между существованием префикса и существованием точного слова крайне важно и часто проверяется.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end  # must be a complete word

t = Trie()
t.insert('apple')
print(t.search('apple'))   # True
print(t.search('app'))     # False (app not inserted)
print(t.search('orange'))  # False

Начинается с (поиск по префиксу)

Метод starts_with проверяет, начинается ли какое-либо вставленное слово с заданного префикса. Он выполняет такой же проход, как search, но вместо проверки is_end возвращает значение «истина», как только успешно пройдены все символы префикса, то есть путь префикса существует в Trie.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True  # prefix path exists

t = Trie()
t.insert('apple')
print(t.starts_with('app'))   # True
print(t.starts_with('ape'))   # False
print(t.search('app'))         # False (not inserted)

Временная и пространственная сложность

Каждая операция Trie (insert, search, starts_with) выполняется за O(m) времени, где m — длина слова: мы проходим не более чем по m вершинам. Пространственная сложность: O(размер алфавита × N × M), где N — количество слов, а M — их средняя длина. На практике общие префиксы значительно уменьшают расход памяти. Словарь children на основе хеш-таблицы занимает меньше места, чем фиксированный массив на 26 символов для разреженных Trie, но поиск в нём имеет немного большие постоянные затраты.

Использование массива вместо словаря

Если используются только строчные английские буквы, применяйте массив фиксированного размера children = [None] * 26 с индексом ord(c) - ord('a'). Такой подход быстрее: поиск дочерней вершины занимает O(1) вместо поиска в хеш-таблице, а размещение данных в памяти предсказуемо. Используйте вариант со словарём, когда набор символов велик или неизвестен, например для Unicode, а вариант с массивом — в задачах соревновательного программирования, где используются только строчные буквы.

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNodeArray()
    
    def insert(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNodeArray()
            node = node.children[idx]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None: return False
            node = node.children[idx]
        return node.is_end

t = TrieArray()
t.insert('cat')
print(t.search('cat'))  # True
print(t.search('car'))  # False

Операция удаления

Удаление из Trie должно обрабатывать три случая: (1) слово отсутствует — ничего не делать; (2) слово существует, но является префиксом другого слова — только сбросить is_end; (3) слово существует и не является префиксом — удалять вершины снизу вверх, остановившись, когда у вершины есть другие дочерние вершины или она является концом другого слова. Удаление редко проверяется на собеседованиях, но полезно понимать его концептуально.

Подсчёт слов по префиксу

Добавьте к каждой вершине поле count, увеличивая его при каждом прохождении вершины во время insert. Чтобы подсчитать слова с заданным префиксом, пройдите до конечной вершины префикса и верните её значение count. Это позволяет выполнять запросы autocomplete за O(m), не обходя всех дочерних вершин, что полезно для расширения реальных систем autocomplete.

class TrieNodeCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # words passing through this node

class TrieCount:
    def __init__(self):
        self.root = TrieNodeCount()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNodeCount()
            node = node.children[c]
            node.count += 1  # increment on each level
        node.is_end = True
    
    def count_with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return 0
            node = node.children[c]
        return node.count

t = TrieCount()
for w in ['apple','app','application','apply']:
    t.insert(w)
print(t.count_with_prefix('app'))   # 4
print(t.count_with_prefix('appl'))  # 3

Сравнение Trie и хеш-таблицы

Хеш-таблица может выполнять точный поиск в среднем за O(m), но не умеет эффективно отвечать на запросы по префиксу: для этого пришлось бы просматривать все ключи. Trie отвечает на запросы по префиксу за O(p), где p — длина префикса, естественным образом группирует слова по общим префиксам и не требует хеширования. Используйте Trie, если нужны частые запросы по префиксу, autocomplete или проверка орфографии. Используйте хеш-таблицу, если требуется только точный поиск.

Trie в реальных системах

Примеры применения Trie в реальных системах: autocomplete (поисковые подсказки Google), проверка орфографии (поиск наиболее близких совпадений), маршрутизация IP (поиск наиболее длинного префикса в маршрутизаторах), предиктивный ввод T9 (устранение неоднозначности символов) и распознаватели DNS (иерархический поиск доменных имён). В каждом случае компромисс между O(m) на операцию и O(ALPHABET × числа вершин) по памяти делает Trie подходящим инструментом для быстрых поисковых операций с учётом префикса при работе с большими объёмами данных.

Быстрая проверка

Проверьте своё понимание концепций «Структуры данных и алгоритмы — подготовка к собеседованиям по программированию» из этого урока.

Итоги урока

В этом уроке вы узнали, что TrieNode содержит словарь children и логическое поле is_end, insert проходит по символам, при необходимости создаёт вершины и устанавливает is_end в конце, а search проверяет is_end, тогда как starts_with проверяет только существование пути префикса. Далее мы подробнее рассмотрим autocomplete по префиксу и метод starts_with.

Часто задаваемые вопросы

Урок «Класс TrieNode: вставка и поиск» бесплатный?

Да — полный текст урока «Класс TrieNode: вставка и поиск» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Класс TrieNode: вставка и поиск»?

Создайте TrieNode со словарём дочерних узлов и флагом is_end, реализуйте вставку и точный поиск и проанализируйте время O(m) на операцию, где m — длина слова Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Класс TrieNode: вставка и поиск»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Coding Interview Prep