Trie — это древовидная структура данных, которая в основном используется для хранения данных, к которым необходимо часто обращаться. Это связано с тем, что это сводит к минимуму сложности поиска, а данные могут быть получены за время O (M), где M — длина данных. Это можно визуализировать с помощью графика.
Этапы построения структуры данных Trie:
- Создайте пустой корневой узел
- Вставьте новые данные в качестве дочерних элементов в корневой узел
- Перед вставкой данных перейдите от корневого узла, чтобы проверить, существуют ли данные уже в Trie. Вставляйте данные только в том случае, если их еще нет.
- Данные всегда вставляются и извлекаются путем перехода от верхних (корневых) к нижним (дочерним) узлам.
- Данные всегда хранятся в порядке сверху вниз без пробелов
Поясним дальше на примере.
Рассмотрим список слов = ["apple", "able", "apps", "bat"]. Структура Trie этого списка будет выглядеть так:
Обратите внимание, что каждый новый символ всегда вставляется из корня. Как и в случае вставки «приложений», мы перешли от корня и обнаружили, что «приложение» уже хранится в Trie. Поэтому мы добавили только «s» в качестве суффикса к «приложению».
Как кодировать структуру данных Trie?
Давайте попробуем закодировать структуру данных Trie на JavaScript. Мы знаем, что каждый узел в Trie представляет (хранит) некоторые данные. Мы можем создать отдельный класс для этого узла, а затем создать несколько его экземпляров, необходимых для создания Trie.
class Node { constructor() { this.children = {}; this.isWordEnd = false; } } class Trie { constructor() { this.root = new Node("root"); // root node of Trie } // insert data to Trie insertData(data) { let current = this.root; for(const d of data){ if (!current.children.hasOwnProperty(d)) { current.children[d] = new Node(); } current = current.children[d]; } current.isWordEnd = true; } // search data in the Trie searchData(data) { let current = this.root; for(const d of data){ if (!current.children.hasOwnProperty(d)) { return false; } current = current.children[d]; } return true; } }
isWordEnd() является необязательным и может использоваться, если мы хотим найти полное слово в Trie.
Случаи использования:
Структура данных Trie имеет несколько вариантов использования. Он используется во многих алгоритмах, которые включают поиск в строках и подстроках. Ниже приведены реальные приложения Trie:
- Автокоррекция мобильной клавиатуры
- Подсказка слова при наборе текста
Структура данных Trie обеспечивает функции поиска, вставки и удаления за время O(M), где M – длина данные и хеширование не требуется.