«1. Обзор

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

Эта статья представляет собой краткое введение в структуру данных trie (произносится как «попробуй»), ее реализацию и анализ сложности.

2. Trie

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. Вставка элементов

Первая операция, которую мы опишем, — это вставка новых узлов.

Прежде чем мы начнем реализацию, важно понять алгоритм:

  1. Set a current node as a root node
  2. Set the current letter as the first letter of the word
  3. If the current node has already an existing reference to the current letter (through one of the elements in the “children” field), then set current node to that referenced node. Otherwise, create a new node, set the letter equal to the current letter, and also initialize current node to this new node
  4. Repeat step 3 until the key is traversed

Сложность этой операции 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. Поиск элементов

Теперь добавим метод для проверки того, присутствует ли определенный элемент в дереве:

  1. Get children of the root
  2. Iterate through each character of the String
  3. Check whether that character is already a part of a sub-trie. If it isn’t present anywhere in the trie, then stop the search and return false
  4. Repeat the second and the third step until there isn’t any character left in the String. If the end of the String is reached, return 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. Удаление элемента

Помимо вставки и поиска элемента, очевидно, что мы также должны иметь возможность удалять элементы.

Для процесса удаления нам необходимо выполнить следующие шаги:

  1. Check whether this element is already part of the trie
  2. If the element is found, then remove it from the 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.