Структурата на данни Trie в Java

Програмиране

1. Общ преглед

Структурите на данните представляват решаващ актив в компютърното програмиране и знанието кога и защо да ги използваме е много важно.

Тази статия е кратко въведение в trie (произнася се „опитайте“) структура на данните, нейното изпълнение и анализ на сложността.

2. Трие

Trie е дискретна структура от данни, която не е добре позната или широко споменавана в типичните курсове по алгоритми, но въпреки това е важна.

Трие (известно още като цифрово дърво), а понякога дори и дърво радикс или дърво на префикс (тъй като те могат да се търсят по префикси), е подредена дървовидна структура, която се възползва от ключовете, които съхранява - обикновено низове.

Позицията на възел в дървото определя ключа, с който е свързан този възел, което прави опити различни в сравнение с бинарни дървета за търсене, в които възел съхранява ключ, който съответства само на този възел.

Всички потомци на възел имат общ префикс на низ, свързан с този възел, докато коренът е свързан с празен низ.

Тук имаме визуализация на TrieNode , която ще използваме при изпълнението на Trie:

public class TrieNode { private HashMap children; private String content; private boolean isWord; // ... }

Може да има случаи, когато трие е двоично дърво за търсене, но като цяло те са различни. И двата бинарни дървета за търсене и опитите са дървета, но всеки възел в двоичните дървета за търсене винаги има две деца, докато възлите на try, от друга страна, могат да имат повече.

В трие всеки възел (с изключение на основния възел) съхранява един знак или цифра. Чрез обхождане на трие от кореновия възел до конкретен възел n , може да се формира общ префикс от символи или цифри, който се споделя и от други клонове на трие.

Чрез обхождане на трие от листен възел до коренния възел може да се формира низ или последователност от цифри.

Ето класът Trie , който представлява изпълнение на структурата от данни на trie:

public class Trie { private TrieNode root; //... }

3. Общи операции

Сега да видим как да приложим основни операции.

3.1. Вмъкване на елементи

Първата операция, която ще опишем, е вмъкването на нови възли.

Преди да започнем изпълнението, важно е да разберем алгоритъма:

  1. Задайте текущ възел като основен възел
  2. Задайте текущата буква като първа буква на думата
  3. Ако текущият възел вече има съществуваща препратка към текущата буква (чрез един от елементите в полето „деца“), тогава задайте текущия възел на този препратен възел. В противен случай създайте нов възел, задайте буквата равна на текущата буква и също инициализирайте текущия възел на този нов възел
  4. Повторете стъпка 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. Намиране на елементи

Нека сега добавим метод за проверка дали даден елемент вече присъства в трие:

  1. Вземете деца на корена
  2. Повтаряйте през всеки знак от низа
  3. Проверете дали този знак вече е част от под-трие. Ако го няма никъде в трие, спрете търсенето и върнете false
  4. Повторете втората и третата стъпка, докато в низа не остане никакъв знак . Ако е достигнат краят на низа , върнете 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. Проверете дали този елемент вече е част от трие
  2. Ако елементът бъде намерен, извадете го от трие

Сложността на този алгоритъм е 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.