Деревья поиска по префиксам
Быстро храните и запрашивайте префиксы слов
«Деревья поиска по префиксам» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Умное хранение слов
Префиксное дерево — это дерево, в котором слова хранятся с общим использованием совпадающих префиксов. Оно молниеносно отвечает на вопросы о префиксах. 🌳
Почему нельзя просто использовать множество
Множество отвечает на запросы по целым словам, а префиксное дерево также обрабатывает запросы по префиксу, например: начинается ли какое-либо слово с pre.
Узлы и рёбра
Каждый узел соответствует позиции в некотором слове, а каждое ребро помечено символом на пути от корня.
Потомки как словарь
В Python проще всего представить узел как словарь, сопоставляющий символ узлу-потомку. Просто и гибко.
root = {}Вставка слова
Чтобы вставить слово, проходите по его символам и создавайте потомка, если его ещё нет.
node = root
for c in word:
node = node.setdefault(c, {})Обозначаем концы слов
После вставки установите флаг окончания, чтобы отличать целое слово от простого префикса.
node['#'] = TrueПоиск целого слова
Чтобы найти слово, переходите по его символам; если какой-либо переход отсутствует, слова нет в структуре. Затем проверьте флаг окончания.
for c in word:
if c not in node:
return False
node = node[c]Проверка префикса
Запрос по префиксу выполняется так же, но проверка флага окончания не нужна. Если Вы дошли до последнего узла, ответ положительный.
Временная сложность
Вставка и поиск требуют O(L), где L — длина слова, независимо от количества сохранённых слов. Важна именно длина.
Подсчёт слов по префиксу
Храните счётчик в каждом узле, чтобы мгновенно узнавать, сколько сохранённых слов имеют заданный префикс.
Где помогают префиксные деревья
Префиксные деревья используются для автодополнения, проверки по словарю и задач на максимальный XOR по битам. Это один из основных инструментов для строковых задач на соревнованиях.
Быстрая проверка
Убедитесь, что Вы понимаете стоимость поиска в префиксном дереве.
Итоги: префиксные деревья освоены
Теперь Вы умеете строить префиксное дерево, вставлять и искать слова за O(L), а также быстро обрабатывать запросы по префиксу и запросы на подсчёт. 🌟
Часто задаваемые вопросы
Урок «Деревья поиска по префиксам» бесплатный?
Да — полный текст урока «Деревья поиска по префиксам» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Деревья поиска по префиксам»?
Быстро храните и запрашивайте префиксы слов Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Деревья поиска по префиксам»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Префиксная функция KMP
- Полиномиальное хеширование строк
- Z-функция для поиска шаблона
- Деревья поиска по префиксам