Определение

Trie — это древовидная структура данных, в которой каждый узел дерева представляет собой массив или список. Trie — это сокращение от извлечение. Попытки объединяют массивы, структуры и указатели вместе. Вы используете данные в качестве дорожной карты для навигации по структуре данных. Если вы сможете проследить эту дорожную карту от начала до конца, вы будете знать, что данные существуют в Trie, в противном случае их нет. Никакие два фрагмента данных не имеют одинаковых дорожных карт. Каждый ключ в Trie гарантированно уникален, а каждое значение является логическим значением, указывающим, существуют ли данные в структуре.

Вот как выглядит Trie Root Node:

Как работает дорожная карта

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

Вставка

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

Например, если вы хотите сохранить первую высадку на Луну в Trie, связанную с годом, когда это произошло. Год (1969) будет ключом для дорожной карты, а значением будет "Высадка на первую луну".

Вот как может выглядеть эта дорожная карта:

Если вы хотите добавить первый запуск космического корабля "Шаттл" (1981), вы можете сделать это следующим образом:

Поиск в Trie

Вы используете цифры ключа для перехода от корня к тому месту, куда вы хотите перейти. По сути, вы создаете указатель обхода для перемещения по Trie. Если вы попали в тупик (нулевой указатель) в любой точке, вы знаете, что элемент не существует. Когда вы дойдете до конца пути, проверьте значение и убедитесь, что это значение, которое вы ищете.

Почему это полезно

Это делает поиск очень быстрым и эффективным.

Вы можете использовать Trie для создания игры Scrabble. В Trie будут храниться все слова, приемлемые для игры, и вы будете искать в Trie введенные пользователем слова, чтобы убедиться, что они находятся в пределах параметров игры.

Проблемы

Из-за того, как построено Trie, они могут занимать много места. Если значения ключей должны быть очень длинными, каждый массив в каждом узле будет очень длинным и, следовательно, займет много места.