Реализация префиксных деревьев в Ruby

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

Что такое префиксное дерево?

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

Основные операции с префиксным деревом

Вставка: добавление новой строки в дерево.
Поиск: проверка, существует ли строка в дереве.
Удаление: удаление строки из дерева.
Поиск по префиксу: получение всех строк, которые начинаются с заданного префикса.

Реализация префиксного дерева на Ruby

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

class TrieNode
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

class Trie
  def initialize
    @root = TrieNode.new
  end

  def insert(word)
    node = @root
    word.each_char do |char|
      node.children[char] ||= TrieNode.new
      node = node.children[char]
    end
    node.is_end_of_word = true
  end

  def search(word)
    node = @root
    word.each_char do |char|
      return false unless node.children[char]

      node = node.children[char]
    end
    node.is_end_of_word
  end

  def delete(word)
    delete_helper(@root, word, 0)
  end

  def delete_helper(node, word, depth)
    return false if node.nil?

    if depth == word.length
      return false unless node.is_end_of_word

      node.is_end_of_word = false
      return node.children.empty?
    end

    char = word[depth]
    should_delete_current_node = delete_helper(node.children[char], word, depth + 1)

    if should_delete_current_node
      node.children.delete(char)
      return node.children.empty? && !node.is_end_of_word
    end

    false
  end

  def starts_with(prefix)
    node = @root
    prefix.each_char do |char|
      return [] unless node.children[char]

      node = node.children[char]
    end
    collect_words(node, prefix)
  end

  def collect_words(node, prefix)
    words = []
    if node.is_end_of_word
      words << prefix
    end

    node.children.each do |char, child_node|
      words.concat(collect_words(child_node, prefix + char))
    end

    words
  end
end

Пример использования префиксного дерева

Теперь, когда мы реализовали класс `Trie`, давайте посмотрим, как его можно использовать для выполнения различных операций.

trie = Trie.new
trie.insert("apple")
trie.insert("app")
trie.insert("banana")

puts trie.search("apple")  # true
puts trie.search("app")    # true
puts trie.search("appl")   # false

trie.delete("apple")
puts trie.search("apple")  # false

puts trie.starts_with("app") # ["app"]
puts trie.starts_with("ban") # ["banana"]

Преимущества использования префиксных деревьев

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

Эффективность поиска: Поиск по префиксу выполняется за O(m), где m — длина префикса.
Экономия памяти: Префиксные деревья могут быть более экономичными по памяти, чем хеш-таблицы, особенно при наличии большого количества общих префиксов.
Упрощение операций: Операции вставки и удаления строк также выполняются за O(m), что делает их эффективными.

Заключение

Префиксные деревья — это мощный инструмент для работы с наборами строк, который может значительно упростить задачи, связанные с поиском и хранением данных. В этой статье мы рассмотрели, как реализовать префиксное дерево на Ruby, а также основные операции, которые можно выполнять с его помощью. Надеемся, что эта информация была полезной и вдохновит вас на использование префиксных деревьев в ваших проектах!