Автор оригинала: Fatos Morina.
1. Обзор
Структуры данных представляют собой важнейший актив в компьютерном программировании, и знание того, когда и зачем их использовать, очень важно.
Эта статья представляет собой краткое введение в структуру данных trie (произносится “try”), ее реализацию и анализ сложности.
2. Трие
Trie-это дискретная структура данных, которая не совсем хорошо известна или широко упоминается в типичных курсах алгоритмов, но тем не менее является важной.
Трие (также известное как цифровое дерево), а иногда даже дерево радиксов или дерево префиксов (поскольку их можно искать по префиксам), представляет собой упорядоченную древовидную структуру, которая использует хранящиеся в ней ключи – обычно строки.
Положение узла в дереве определяет ключ, с которым связан этот узел, что делает его отличным от бинарных деревьев поиска, в которых узел хранит ключ, соответствующий только этому узлу.
Все потомки узла имеют общий префикс String , связанный с этим узлом, в то время как корень связан с пустой строкой .
Здесь у нас есть предварительный просмотр Treenode , который мы будем использовать в нашей реализации Trie:
public class TrieNode {
private HashMap children;
private String content;
private boolean isWord;
// ...
} Могут быть случаи, когда trie представляет собой двоичное дерево поиска, но в целом это разные случаи. И деревья двоичного поиска, и деревья являются деревьями, но каждый узел в деревьях двоичного поиска всегда имеет двух дочерних элементов, в то время как узлы попыток, с другой стороны, могут иметь больше.
В дереве каждый узел (кроме корневого узла) хранит один символ или цифру. При прохождении триэ вниз от корневого узла к конкретному узлу n может быть сформирован общий префикс символов или цифр , который также является общим для других ветвей триэ.
Проходя вверх по трие от конечного узла к корневому узлу, можно сформировать Строку или последовательность цифр.
Вот класс Trie , который представляет собой реализацию структуры данных trie:
public class Trie {
private TrieNode root;
//...
}3. Общие операции
Теперь давайте посмотрим, как реализовать основные операции.
3.1. Вставка Элементов
Первая операция, которую мы опишем, – это вставка новых узлов.
Прежде чем мы начнем реализацию, важно понять алгоритм:
- Установите текущий узел в качестве корневого узла
- Установите текущую букву в качестве первой буквы слова
- Если текущий узел уже имеет существующую ссылку на текущую букву (через один из элементов в поле “дочерние элементы”), установите текущий узел на этот ссылочный узел. В противном случае создайте новый узел, установите букву, равную текущей букве, а также инициализируйте текущий узел для этого нового узла
- Повторяйте шаг 3 до тех пор, пока ключ не будет пройден
Сложность этой операции заключается в O(n) , где n представляет размер ключа.
Вот реализация этого алгоритма:
public void insert(String word) {
TrieNode current = root;
for (char l: word.toCharArray()) {
current = current.getChildren().computeIfAbsent(l, c -> new TrieNode());
}
current.setEndOfWord(true);
}Теперь давайте посмотрим, как мы можем использовать этот метод для вставки новых элементов в три:
private Trie createExampleTrie() {
Trie trie = new Trie();
trie.insert("Programming");
trie.insert("is");
trie.insert("a");
trie.insert("way");
trie.insert("of");
trie.insert("life");
return trie;
}Мы можем проверить, что племя уже было заполнено новыми узлами из следующего теста:
@Test
public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() {
Trie trie = createTrie();
assertFalse(trie.isEmpty());
}3.2. Поиск Элементов
Теперь давайте добавим метод, чтобы проверить, присутствует ли конкретный элемент уже в трие:
- Получить детей от корня
- Повторите каждый символ строки
- Проверьте, является ли этот символ уже частью подтрибы. Если его нет нигде в трие, то прекратите поиск и верните false
- Повторяйте второй и третий шаги до тех пор, пока в строке не останется ни одного символа. Если достигнут конец строки /, верните true
Сложность этого алгоритма заключается в O(n) , где n представляет длину ключа.
Реализация Java может выглядеть следующим образом:
public boolean find(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord();
}И в действии:
@Test
public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() {
Trie trie = createExampleTrie();
assertFalse(trie.containsNode("3"));
assertFalse(trie.containsNode("vida"));
assertTrue(trie.containsNode("life"));
}3.3. Удаление элемента
Помимо вставки и поиска элемента, очевидно, что мы также должны иметь возможность удалять элементы.
Для процесса удаления нам необходимо выполнить следующие действия:
- Проверьте, является ли этот элемент уже частью trie
- Если элемент найден, то удалите его из трие
Сложность этого алгоритма равна O(n) , где n представляет длину ключа.
Давайте быстро взглянем на реализацию:
public void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode current, String word, int index) {
if (index == word.length()) {
if (!current.isEndOfWord()) {
return false;
}
current.setEndOfWord(false);
return current.getChildren().isEmpty();
}
char ch = word.charAt(index);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord();
if (shouldDeleteCurrentNode) {
current.getChildren().remove(ch);
return current.getChildren().isEmpty();
}
return false;
}И в действии:
@Test
void whenDeletingElements_ThenTreeDoesNotContainThoseElements() {
Trie trie = createTrie();
assertTrue(trie.containsNode("Programming"));
trie.delete("Programming");
assertFalse(trie.containsNode("Programming"));
}4. Заключение
В этой статье мы увидели краткое введение в структуру данных trie, ее наиболее распространенные операции и их реализацию.
Полный исходный код примеров, приведенных в этой статье, можно найти на GitHub .