Вы когда-нибудь шли на очень важное собеседование, сожалея о том, что не изучили структуру данных Trie Tree? Ну лучше поздно, чем никогда. В этой статье я объясню, как реализовать средство сопоставления префиксов с использованием структуры данных Trie Tree за 3 быстрых шага, чтобы вы могли понять, как реализовать и использовать структуру данных Trie Tree.

Полная реализация доступна здесь.

Я буду использовать язык Java, если вы хотите увидеть это на других языках, вы можете написать мне, и я попытаюсь сделать это на другом языке.

Часть 1. Реализация структуры данных Trie

Сначала попробуем понять, что такое Trie Tree, а затем реализуем его. Я предлагаю вам подумать о том, как реализовать структуру данных, понимая, что это такое.

Посмотрев на эту простую диаграмму ниже, вы поймете, что дерево дерева — это, по сути, дерево поиска слов, обычно используемое для сопоставления префиксов. Он состоит из корневого узла и дочерних узлов, как бинарное дерево или B-дерево, каждый узел содержит букву из алфавита. Как вы можете себе представить, каждый уровень дерева в основном является приоритетом буквы в слове, слово пишется от walk от корня до конца leave (дочерний узел без дочерних узлов).

Теперь, когда мы понимаем, что такое дерево дерева, как нам его реализовать?

Мы знаем, что каждый узел может иметь любой из 26 алфавитов в качестве дочернего узла, поэтому дочерние элементы узла будут представлены массивом из 26 узлов Trie. Мы инициализируем один из 26 узлов, если буква существует, в противном случае дочерний узел будет нулевым.

Я принял решение создать функцию для инициализации дочерних узлов вместо того, чтобы делать это в конструкторе, потому что мне нужна возможность не инициализировать дочерние узлы и занимать место, если мне это не нужно.

Теперь узел Trie Tree выглядит следующим образом.

Далее давайте реализуем дерево с помощью функции вставки, чтобы мы могли построить дерево. Конечно, вы также можете реализовать другие функции, такие как поиск и удаление и т. д., но это необязательно. Я также построил поиск ниже.

Чтобы вставить слово, мы просто преобразуем каждую букву в целое число и инициализируем узел Trie в соответствующем целочисленном положении в массиве дочерних элементов текущего узла, а затем перемещаем текущий узел в дочерний узел, чтобы продолжить движение вниз по дереву.

Пока все выглядит хорошо, но вскоре мы обнаружим, что что-то не так, и обсудим исправление в третьей части.

Часть 2. Создание функции сопоставления префиксов

Созданная мной функция сопоставления префиксов принимает два входа: дерево с уже вставленными словами и префикс. Он возвращает список совпадающих строк слов.

Сначала мы находим, где заканчивается префикс в дереве, поэтому для каждой буквы в префиксе мы проверяем, не является ли она нулевой в дереве, и переходим к соответствующей букве дочернего узла. Если мы не находим совпадений для префикса, мы возвращаем пустой список слов.

Затем мы создаем вспомогательную функцию для обхода всех дочерних элементов, начиная с данного узла Trie, и помещаем ее в список слов. Возможно, вам придется потратить некоторое время, чтобы подумать о том, как сделать эту часть, как это сделал я. Я сделал это рекурсивно. Если у вас возникли проблемы с выполнением этой части, я предлагаю вам воспользоваться LeetCode и решить некоторые проблемы с рекурсией в древовидной структуре данных, чтобы помочь вам в этом.

Часть 3. Тестирование и понимание того, что реализация не идеальна

Я протестировал свою реализацию с последующим и понял, упс, текущая реализация учитывает только слова, у которых есть конечный дочерний узел в дереве. Такие слова, как answer и any, найдены, а an и a – нет.

Итак, как мы это исправим? Если вы посмотрите на приведенную ниже диаграмму, вы поймете, что если мы отслеживаем количество каждой буквы в узле Trie и их дочерних элементов, если количество букв больше, чем количество дочерних элементов в узле, то существует конец слова в текущем узле.

Что ж, исправить это легко, мы следим за каждой вставкой букв и их дочерними элементами и добавляем слово всякий раз, когда есть конец.

Мы увеличиваем количество дочерних элементов в текущем узле и количество букв в дочернем узле при каждой вставке.

Не забудьте добавить оператор if о том, что если количество дочерних элементов меньше количества букв, добавьте слово в обход узла Trie.

Теперь снова тестируем и убеждаемся, что реализация работает.

Я не планировал, что урок будет таким длинным, но, надеюсь, он был эффективным. Если у вас есть какие-либо вопросы или вы хотите, чтобы я объяснил или реализовал другие проблемы, вы можете написать мне или написать мне напрямую по адресу [email protected].

Это мой Github: https://github.com/chenleishen

Спасибо за чтение!