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 – длина данные и хеширование не требуется.