Реализовать 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, чтобы открывать для себя самые красивые места по всему миру с тщательно подобранным контентом. Проверьте это!