«Алгоритмы и структуры данных» Красота деревьев деревьев

предисловие

Дерево TRIE TRIE DEAL - это ветвь темы структуры данных. Понимание структуры данных типа дерева TRIE поможет создать систему знаний алгоритмов и структур данных.

Мое понимание дерева Trie: объединение строк, устранение ненужного хранилища и использование общего префикса строк.

На самом деле для его понимания можно понять это предложение👇

Используйте общий префикс строк, чтобы сократить время запроса и свести к минимуму ненужные сравнения строк.Эффективность запросов выше, чем у хеш-деревьев.

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

Затем мы представим дерево Trie вокруг следующих точек👇

основная концепция
основная природа
Сценарии применения
2 примера вопросов

Свяжитесь с 👉TianTianUp, если у вас возникнут проблемы, вы можете связаться с автором, я готов сопровождать вас, чтобы вместе изучить и обсудить проблему.

основная концепция

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

Давайте посмотрим на его описание в Википедии ⬇️

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

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

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

Можно обнаружить, что это словарное дерево использует ребра для представления букв, иПуть от корневого узла к узлу в дереве представляет собой строку. Например, 1→2→6 представляет строкуaba.

Другой пример,1→4→8Сформированная строкаca, то если мы расширим вниз, у нас естьcaa,cab, то они пройдут через1→4→8, эти пути указывают, что они имеют общий префикс, и содержимое этого префиксаca, сказано здесь, мы знаем, что дерево словаря использует префикс строки для решения проблемы.

Итак, каковы его специфические свойства, мы представим их ниже ~

основная природа

Поскольку приведенные выше концепции имеют определенное понимание, мы рассмотрим основную природу следующего дерева Trie.

В соответствии с этим его можно условно разделить на три пункта.

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

Далее мы можем немного проанализировать это, и мы можем объединить это с картинкой, чтобы увидеть👇

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

(Источник картинки неизвестен, слишком много ссылок в интернете~)

Первое свойство:

Из рисунка также видно, что корневой узел/, Представленное содержимое также пусто, другие узлы, такие как следующий уровень корневого узла, имеютhа такжеs, которые представляют два символа соответственно.

Второе свойство:

От корневого узла к определенному узлу символы, проходящие по пути, соединяются, образуя строку, соответствующую узлу.

Напримерhowпредставляет строку,hi, также представляет собой строку, но будет ли вам любопытно,heа такжеhelПочему он не может представлять строку?

Когда вы думаете об этом, это означает, что вы видели его очень внимательно, и вы собираетесь его освоить. Действительно, по картинке мы обнаружим, что некоторые узлы имеют разные цвета. Это потому, что мы планировали использовать этот темный node для представления Текущий конец строки, подумайте об этом, каков эффект от этого?

Итак, в реальном коде, как мы должны согласиться или сделать метку?На самом деле нам нужно только установить бит метки.

Например, следующее 👇

const TrieNode = function () {
  this.next = Object.create(null)
  this.isEnd = false
};

Текущая переменная isEnd указывает, является ли текущий узел конечной строкой.Если isEnd имеет значение True, это означает, что строка, сформированная от корневого узла до этого символа, существует и является полной строкой.

Третье свойство:

Все дочерние узлы каждого узла содержат разные строки.

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

Сценарии применения

После определенного понимания дерева Trie мы можем увидеть, какие у него есть практические сценарии применения.

Вот несколько точек, предоставленных в Интернете для ознакомления 👇

В поисковой системе запросит ключевое слово, и система автоматически выдаст выпадающий список для соответствия ключевым словам.Этот сценарий применения должен быть знаком всем.

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

Поиск строки

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

10 миллионов строк, некоторые из которых являются дубликатами, необходимо удалить все дубликаты и сохранить строки без дубликатов.
Учитывая список знакомой лексики, состоящий из N слов, и статью, написанную строчными буквами английского языка, напишите все новые слова, которых нет в списке знакомой лексики, в самом раннем порядке.

Статистика частотности слов

Учитывая очень длинную строку, подсчитайте, например, наиболее частые вхождения👇

Есть файл размером 1G, каждая строка в нем это слово, размер слова не превышает 16 байт, а размер лимита памяти 1M. Возвращает 100 наиболее часто встречающихся слов.
Для подсчета 10 самых часто встречающихся слов требуется текстовый файл, содержащий около 10 000 строк и по одному слову в строке.

Строка самого длинного общего префикса

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

Если вам нужно привести пример, вот пример👇

Учитывая N строк строчных английских букв и Q запросов, то есть какова длина самого длинного общего префикса двух строк?

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

2 примера

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

Самое длинное слово в словаре⭐

Связь:самое длинное слово в словаре

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

Если ответа нет, возвращается пустая строка.

Пример 1:

输入：
words = ["w","wo","wor","worl", "world"]
输出："world"
解释： 
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

Пример 2:

输入：
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释：
"apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。

намекать:

Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/длиннейшее-слово-в-словаре Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

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

Правильно, префиксы одинаковые.С этой точки зрения можно ли использовать это дерево префиксов для хранения своих данных?
Затем снова пройдитесь по дереву, пока дерево имеет только одну ветвь, это означает, что оно имеет решение, если ветвей больше двух, ответа нет.

Анализ сложности

Это должно быть хорошо понято, поэтому я опускаю это здесь.

В данном случае мое решение строит словарное дерево.Конечно, есть и другие решения.Я не буду его здесь раскрывать.Можете посмотреть мой код~

код нажмите здесь☑️

На самом деле вы обнаружите, что построение Trie-дерева занимает много места, а это означает, что пространство обменивается на время, поэтому проблема должна решаться в соответствии с реальной проблемой.

Реализовать Trie (дерево префиксов) ⭐⭐

Связь:Реализовать Trie (дерево префиксов)

Реализуйте Trie (дерево префиксов), содержащее три операции: вставка, поиск и запуск с помощью.

Пример:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

проиллюстрировать:

Вы можете предположить, что все входные данные состоят из строчных букв a-z.
Все входные данные гарантированно будут непустыми строками.

Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/implement-trie-prefix-tree Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.

Эта тема представляет собой типичное написание Trie-дерева.Если вы пишите эту тему впервые, если вы понятия не имеете, вы можете попробовать сначала посмотреть код других людей, чтобы увидеть основные套路Где.

Нечего сказать, вы можете обратиться к этому коду, чтобы увидеть, как построить дерево словарей👇

leetcode-实现Trie树 — leetcode - реализует дерево Trie

Код нажмите здесь ☑️

Остальную операцию удаления, а также частоту появления статистических строк можно реализовать самому, это в принципе не сложно, просто нарисуй картинку и будешь знать как это реализовать~

Вопросы бесконечны. После ответа на эти вопросы, я надеюсь, вы сможете получить некоторое представление о словарном дереве Trie и глубже понять его ~ Далее я подготовил четыре набора вопросов, надеюсь, они будут вам полезны ~

самое длинное слово в словаре

Реализовать Trie (дерево префиксов)

Поиск слов 2

Loading question

❤️ Всем спасибо

Если вы считаете этот контент полезным:

Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
Обратите внимание на публичный аккаунтИнтерфейс UpUp, свяжитесь с автором, если у вас возникнут какие-либо проблемы, пожалуйста, беспокойте меня, мы обсудим и добьемся прогресса вместе.
Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):

В этой статье используетсяmdniceнабор текста