Реализовать Trie в JavaScript
Поработав с сайтами, которые ежегодно посещают более 50 миллиардов веб-сайтов с Higglo Digital, я пишу на технические темы и учу инженеров иметь прочную основу, которая поможет им продвинуться по карьерной лестнице. Я также создаю потрясающие продукты для цифровых кочевников — посмотрите!
Попытки, также известные как деревья префиксов, представляют собой структуру данных, используемую для эффективного хранения и поиска строк. Они обычно используются в таких приложениях, как средства проверки орфографии и функции автозаполнения.
Идея, лежащая в основе дерева, состоит в том, чтобы хранить каждый символ строки в отдельном узле, при этом корневой узел представляет собой начало строки. Каждый узел также имеет несколько дочерних элементов, представляющих возможные следующие символы в строке. Это позволяет быстро искать и вставлять строки, поскольку количество узлов, необходимых для достижения строки, равно длине строки.
В JavaScript мы можем реализовать trie, используя объекты для представления узлов. Каждый узел будет иметь свойство, называемое «дети», которое представляет собой объект, содержащий следующий символ в качестве ключа и дочерний узел в качестве значения. У узла также будет свойство «конец», которое указывает, представляет ли узел конец строки.
Чтобы вставить строку в дерево, мы начинаем с корневого узла и повторяем каждый символ строки. Для каждого символа мы проверяем, существует ли персонаж как дочерний элемент текущего узла. Если это так, мы переходим к этому ребенку. Если это не так, мы создаем нового потомка для этого персонажа и переходим к нему. Как только мы достигаем конца строки, мы устанавливаем для свойства «конец» текущего узла значение true.
Чтобы найти строку в дереве, мы следуем аналогичному процессу. Мы начинаем с корневого узла и перебираем каждый символ строки, переходя к дочернему узлу, соответствующему этому символу. Если мы достигнем конца строки и свойство «конец» текущего узла истинно, то строка существует в дереве. Если мы достигнем конца строки, а свойство «конец» будет ложным, или если мы достигнем узла без дочернего элемента для следующего символа, тогда строка не существует в дереве.
Одним из полезных применений дерева является поиск всех строк в дереве, начинающихся с определенного префикса. Для этого мы можем выполнить поиск префикса и вернуть все строки, которые являются дочерними элементами конечного узла, достигнутого во время поиска.
Вот реализация попытки в JavaScript:
class TrieNode { constructor(value) { this.value = value; this.children = {}; this.isEnd = false; } } class Trie { constructor() { this.root = new TrieNode(null); } insert(word) { let current = this.root; for (let i = 0; i < word.length; i++) { let ch = word[i]; if (!(ch in current.children)) { current.children[ch] = new TrieNode(ch); } current = current.children[ch]; } current.isEnd = true; } search(word) { let current = this.root; for (let i = 0; i < word.length; i++) { let ch = word[i]; if (!(ch in current.children)) { return false; } current = current.children[ch]; } return current.isEnd; } startsWith(prefix) { let current = this.root; for (let i = 0; i < prefix.length; i++) { let ch = prefix[i]; if (!(ch in current.children)) { return false; } current = current.children[ch]; } return true; } }
Чтобы использовать эту реализацию, вы можете создать новое дерево и вставить в него слова, используя метод insert
. Затем вы можете использовать метод search
, чтобы проверить, существует ли слово в дереве, или метод startsWith
, чтобы проверить, существует ли префикс в дереве.
Например:
let trie = new Trie(); trie.insert("cat"); trie.insert("car"); trie.insert("bat"); console.log(trie.search("cat")); // true console.log(trie.search("car")); // true console.log(trie.search("bat")); // true console.log(trie.search("cab")); // false console.log(trie.startsWith("ca")); // true console.log(trie.startsWith("ba")); // true console.log(trie.startsWith("c")); // true console.log(trie.startsWith("b")); // true console.log(trie.startsWith("d")); // false
Попытки представляют собой полезную структуру данных для эффективного хранения и поиска строк. Они обычно используются в таких приложениях, как средства проверки орфографии и функции автозаполнения, и могут быть легко реализованы в JavaScript с использованием объектов для представления узлов.
Я основал Higglo Digital, и мы можем помочь вашему бизнесу сокрушить веб-игры с помощью отмеченного наградами веб-сайта и передовой цифровой стратегии. Если вы хотите увидеть красиво оформленный веб-сайт, загляните к нам.
Я также создал Wanderlust Extension, чтобы открывать для себя самые красивые места по всему миру с тщательно подобранным контентом. Проверьте это!