Введение

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

Это особенно полезно в случаях, когда требуется поиск и сопоставление префиксов внутри строк.

1. Если я расскажу вам об алгоритме Trie, этот алгоритм может вас заинтересовать, а может и не заинтересовать

2. Но если бы я сказал вам, что вы можете создать алгоритм автозаполнения с помощью этого. вам будет еще интереснее узнать это.

Пример использования этого алгоритма

1. Автозаполнение:

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

2. Проверка орфографии:

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

3. IP-маршрутизация:

а. Попытки используются в маршрутизаторах для хранения таблиц маршрутизации.
б. Маршрутизатор использует попытку для сопоставления самого длинного префикса, который определяет следующий переход для пакета.

4. Эффективное хранение и поиск строк:

а. Если у вас есть набор данных строк с множеством общих префиксов, дерево может хранить эти строки, используя меньше места, чем их хранение по отдельности.
б. Операция поиска также эффективна: ее временная сложность пропорциональна длине искомой строки.

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

class Trie {
    constructor() {
        this.root = new Node ();
    }

    insert(word) {
        let head = this.root;

        for (let i = 0; i ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

Не стесняйтесь обращаться ко мне, если у вас есть какие-либо проблемы/вопросы.