1. Введение
1. Оригинальный текст этой статьи взят из задачи алгоритма на leetcode.Implement Trieрешение.
2.исходный адрес
3. Новичок уродлив, надеюсь, все смогут постучать~ (улыбается)
Во-вторых, оригинальный текст здесь
1. Описание проблемы
Вопросы по алгоритму:
Дерево дерева завершается путем написания таких методов, как вставка, запрос и определение начала.
пример:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
намекать:
- Вы можете предположить, что все входные данные состоят из строчных букв a-z.
- Все массивы входных строк не пусты.
Суммировать:
Эта статья написана для читателей среднего уровня и познакомит вас со структурой данных trie (деревом префиксов) и общими операциями внутри нее.
2. Решение:
2.1 Применение:
Trie (дерево префиксов) — это древовидная структура данных, которая часто используется для извлечения ключевого слова в наборе строк данных. В настоящее время структура данных trie эффективно применяется во многих областях:
(1) Автозаполнение
(2) Проверка орфографии
(3) IP-маршрутизация (сопоставление самого длинного маршрута)
Есть много других структур данных, таких как сбалансированные деревья, хеш-таблицы, которые могут искать слова в наборе строковых данных, но почему мы используем trie? Хотя хеш-таблице нужно только найти ключO(1) временная сложность, но в следующих операциях это не очень эффективно.
- Найдите все ключи с общим префиксом.
- Перечислить все строки лексикографически
Еще одна причина, по которой trie лучше, чем хеш-таблица, заключается в том, что после увеличения размера данных хеш-таблицы будет много хэш-коллизий, поэтому сложность времени запроса будет увеличена доO (n),nколичество вставленных ключевых слов. По сравнению с хэш-таблицей, trie требует меньше места при хранении большого количества ключевых слов с общим префиксом. В этом примере требуется толькоO(m) временная сложность (mдлина ключевого слова). Чтобы запросить ключевое слово в сбалансированном дереве, вам нужно потратитьO (m logn)
2.2 структура узла trie
Trie — это корневое дерево, и его узлы имеют следующие поля:
- Существует не более R соединений с дочерними узлами, и каждое соединение соответствует одной из R букв. Буквы R происходят из алфавита. В этом посте мы предполагаем, что R равно 26, то есть 26 строчным латинским буквам.
- Логическое значение isEnd, указывающее, указывает ли логическое значение, является ли текущий узел концом ключевого слова, иначе это просто префикс ключевого слова.
Рис. 6. Представляет выражение ключевого слова «leet» в дереве
узел trie, написанный на java
class TrieNode {
// R links to node children
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
public TrieNode() {
links = new TrieNode[R];
}
public boolean containsKey(char ch) {
return links[ch -'a'] != null;
}
public TrieNode get(char ch) {
return links[ch -'a'];
}
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}
2.3 Наиболее распространенные операции в trie — добавление и запрос ключевых слов
(1) Добавьте ключевые слова в список
Мы вставляем ключевые слова, обходя дерево. Мы начинаем с корневого узла и ищем соединение, соответствующее первой букве ключевого слова.Здесь обычно есть два случая:
- Если связь существует, то мы опускаем эту связь на следующий подуровень, а затем ищем связь, соответствующую следующей букве ключевого слова.
- Если соединение не существует, мы создаем новый узел дерева, соответствующий текущей букве ключевого слова, чтобы установить соединение с родительским узлом.
Мы повторяем этот шаг до тех пор, пока не будет обработана последняя буква ключевого слова, а затем помечаем последний узел как конечный узел. Алгоритм заканчивается.
Вставить метод, написанный на java
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
}
Анализ сложности:
- временная сложностьO(m),mдлина ключевого слова. На каждой итерации алгоритма мы либо проверяем узел, либо создаем новый, вплоть до последней буквы ключевого слова. Итак, для этого требуется только m операций.
- Пространственная сложность O(m). В худшем случае вновь вставленные ключевые слова и ключевые слова, которые уже существуют в дереве, не имеют общего префикса, поэтому нам нужно вставить m новых узлов, что потребует O(m) пространственной сложности.
(2) Поиск ключевых слов в дереве
Каждое ключевое слово в дереве может быть представлено путем от корневого узла к дочерним узлам. Мы будем искать в корневом узле по первой букве ключевого слова, а затем проверять соответствующую букву каждого соединения на узле.Обычно есть два случая:
- Есть ссылка, соответствующая букве ключевого слова, мы перейдем от этой ссылки к следующему узлу и будем искать ссылку, соответствующую следующей букве ключевого слова.
- Соответствующее соединение не существует.Если последняя буква ключевого слова была пройдена в это время, текущий узел помечается как конечный узел, а затем возвращается true. Конечно, есть еще два случая, когда мы вернули бы false:
- Буквы ключевого слова не были пройдены, но нет возможности найти путь, образованный буквами ключевого слова в дереве, поэтому ключевое слово не существует в дереве.
- Буквы ключевого слова были пройдены, но текущий узел не является конечным узлом, поэтому искомое ключевое слово является только префиксом ключевого слова в дереве.
class Trie {
...
// search a prefix or whole key in trie and
// returns the node where search ends
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
}
Анализ сложности:
- Временная сложность: O(m). Каждый шаг алгоритма заключается в поиске следующей буквы ключевого слова, поэтому в худшем случае алгоритм должен выполнить m шагов.
- Пространственная сложность: O(1).
(3) Поиск префикса ключевого слова в дереве
Этот метод очень похож на метод, который мы используем для поиска ключевых слов в дереве. Мы двигаемся от корневого узла до тех пор, пока не будет найдена каждая буква префикса ключевого слова, или нет возможности найти следующий путь в дереве на основе текущей буквы ключевого слова. Единственная разница между этим методом и вышеупомянутым ключевым словом поиска заключается в том, что когда мы переходим к последней букве префикса ключевого слова, мы всегда возвращаем true, нам не нужно учитывать, имеет ли текущий узел конечный флаг, потому что мы просто ищем Префикс ключевого слова, а не все ключевое слово.
Написанный на java метод для поиска префиксов ключевых слов
class Trie {
...
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
Анализ сложности:
- Временная сложность: O(м)
- Космическая сложность: O(1)
3. Проблемы с приложением
Вот несколько очень подходящих задач для практики, и эти задачи можно решить с помощью структуры данных trie.
- Добавление и поиск слов (дизайн структуры данных)- Очень простое применение try.
- поисковое слово 2——Похоже на игру boggle
Этот анализ исходит от @elmirap