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. Вмъкване на елементи
Първата операция, която ще опишем, е вмъкването на нови възли.
Преди да започнем изпълнението, важно е да разберем алгоритъма:
- Задайте текущ възел като основен възел
- Задайте текущата буква като първа буква на думата
- Ако текущият възел вече има съществуваща препратка към текущата буква (чрез един от елементите в полето „деца“), тогава задайте текущия възел на този препратен възел. В противен случай създайте нов възел, задайте буквата равна на текущата буква и също инициализирайте текущия възел на този нов възел
- Повторете стъпка 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. Изтриване на елемент
Освен вмъкването и намирането на елемент, очевидно е, че ние също трябва да можем да изтриваме елементи.
За процеса на изтриване трябва да следваме стъпките:
- Проверете дали този елемент вече е част от трие
- Ако елементът бъде намерен, извадете го от трие
Сложността на този алгоритъм е 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.