1. Обзор
Структуры данных представляют собой важнейший актив в компьютерном программировании, и очень важно знать, когда и зачем их использовать.
Эта статья представляет собой краткое введение в структуру данных trie (произносится как «попробуй»), ее реализацию и анализ сложности.
2. Попробуйте
Trie — это дискретная структура данных, которая не очень хорошо известна или широко упоминается в типичных курсах по алгоритмам, но, тем не менее, важна.
Древовидное дерево (также известное как цифровое дерево), а иногда даже базисное дерево или дерево префиксов (поскольку в них можно искать по префиксам) — это упорядоченная древовидная структура, которая использует хранящиеся в ней ключи — обычно строки.
Положение узла в дереве определяет ключ, с которым связан этот узел, что отличает попытки от бинарных деревьев поиска, в которых узел хранит ключ, соответствующий только этому узлу.
Все потомки узла имеют общий префикс строки , связанный с этим узлом, тогда как корень связан с пустой строкой.
Здесь у нас есть предварительный просмотр TrieNode , который мы будем использовать в нашей реализации Trie:
public class TrieNode {
private HashMap<Character, TrieNode> 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);
}
Теперь давайте посмотрим, как мы можем использовать этот метод для вставки новых элементов в trie:
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;
}
Мы можем проверить, что 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. Удаление элемента
Помимо вставки и поиска элемента, очевидно, что мы также должны иметь возможность удалять элементы.
Для процесса удаления нам необходимо выполнить следующие шаги:
- Проверьте, не является ли этот элемент частью дерева.
- Если элемент найден, то удалить его из дерева
Сложность этого алгоритма 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 .