fПопробуйте попытки.

Попытки – это особый вид дерева.

Напоминание о деревьях…

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

Деревья имеют несколько характеристик, определяющих способ организации данных. Во-первых, у них есть единственный узел (называемый корнем), который действует как точка входа для всего дерева. Во-вторых, каждый узел может иметь ровно один родительский узел (кроме корня, у которого нет родителя). И в-третьих, узлы не могут зацикливаться и указывать на узлы выше (или ближе к корню, поскольку деревья данных растут вверх ногами), чем они есть.

Хотя все деревья обладают этими качествами, разные типы деревьев различаются количеством дочерних узлов и способом присвоения данных этим дочерним узлам. Например, каждый узел в двоичном дереве может иметь не более двух дочерних узлов (левого и правого). В двоичном дереве поиска данные организованы таким образом, что каждое значение, хранящееся в левой ветви узла, меньше, чем каждое значение, хранящееся в правой ветви узла.

Все это делает различные типы (а их очень много) деревьев невероятно эффективными инструментами для организации и манипулирования большими наборами данных.

Итак… Пытается?

Произношение

Создатель дерева три подумал, что было бы мило назвать свое творение словом retrieval(потому что для этого удобно). И поэтому он произнес это одинаково: 'дерево', что излишне сбивает с толку. Произносите это как 'try', если только вы не из тех людей, которые разбрасываются такими словами, как древесность.

Состав

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

Представьте, что у вас есть строка: «dumbleedoo». Он состоит из строчных букв латинского алфавита. В нем нет ни заглавных букв, ни специальных символов, ничего особенного. Если вы хотите реализовать попытку для хранения этой строки и подобных ей строк, каждый узел может иметь до 26 дочерних узлов (поскольку в каждом индексе строки может присутствовать 26 возможных символов).

Trie Nodes — что в них есть?

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

Что может показаться вам интересным, так это то, что узлу не нужно хранить значение, представляющее символ, с которым он связан. Это потому, что хранимый символ является неявным; поскольку единственный способ добраться до узла — использовать символ в качестве ключа от родительского узла, нет необходимости хранить сам символ внутри узла.

(Тем не менее, некоторые попытки действительно сохраняют данные, связанные со строкой ключа, просто помните, что это не существенно для структуры дерева.)

Пример!

Начнем с одного узла дерева. У него нет родителей, и мы назовем его корнем. Сейчас мы ничего не храним в дереве, поэтому у него тоже нет дочерних элементов. Он отдыхает один, ест ужин в микроволновке перед телевизором и может держать, а может и не держать птиц. Звучит неплохо!

Наша первая вставка

Допустим, мы хотим сохранить слово в этом дереве. Это слово CAB. Первое, что мы сделаем, — это создадим новый узел как дочерний по отношению к корневому узлу и сохраним указатель на этот дочерний узел в нашем наборе дочерних узлов по ключу C. Затем мы перейдем к этому новому узлу и проверим следующую букву в нашей строке. Это A, поэтому мы повторим процесс инициализации нового узла и сохраним указатель в наборе дочерних элементов C по ключу A. >. И так до B,, чтобы каждая буква нашей строки имела узел, который является дочерним по отношению к предыдущей букве.

Когда мы доходим до конца строки (в данном случае B), мы устанавливаем логическое значение этого узла в true, указывая, что мы достигли конца строки. слово (на рисунке ниже вы можете видеть, что я покрасил узел в красный цвет).

Добавляем больше слов

Безудержное веселье! Давай сделаем это снова. На этот раз мы добавим слово УТКА.

Duck не начинается с C,, поэтому мы инициализируем новый узел из корня по ключу D.

Следуя предыдущим шагам, мы создаем дочерний узел для каждой буквы и отмечаем последнюю букву как конец слова.

Вот где происходит волшебство

Что произойдет, если мы захотим добавить еще одно слово, скажем… СЫР, которое начинается с той же буквы, что и одно из слов, которые мы уже сохранили?

Я очень рад, что вы спросили.

Мы сидим в корневом узле, смотрим на первую букву CHEESE и понимаем, что у нас уже есть дочерний узел, инициализированный для ключа C. Так что ничего нового мы здесь не создаем. Мы просто следуем по указателю от корня до C-узла.

Теперь строки расходятся, и мы следуем нашим обычным действиям, создавая нового дочернего элемента для H и так далее, пока не отметим конец слова на последней букве E.

Легкий!

Но подумайте о последствиях добавления такого слова, как КАПУСТА, к нашему существующему дереву: каждая из первых трех букв указывает на существующие узлы C, A и B из CAB.

class TrieNode
  attr_reader :value, :children
  attr_accessor :word

  def initialize(value)
    @value = value

    @word = false
    @children = []
  end
end

class Trie
  def initialize
    @root = TrieNode.new(nil)
  end

  def add_word(word)
    letters = word.chars
    node = @root

    letters.each { |letter| node = add_character(letter, node.children) }

    node.word = true
  end

  def find_word(word)
    letters = word.chars
    node = @root

    word_found =
      letters.all? { |letter| node = find_character(letter, node.children) }

    yield word_found, node if block_given?

    node
  end

  def include?(word)
    find_word(word) { |found, base| return found && base.word }
  end

  private

  def add_character(character, node)
    node.find { |n| n.value == character } || add_node(character, node)
  end

  def find_character(character, node)
    node.find { |n| n.value == character }
  end

  def add_node(character, node)
    TrieNode.new(character).tap { |new_node| node << new_node }
  end
end