Struktura danych Trie w Javie

Przegląd

Struktury danych stanowią kluczowy atut w programowaniu komputerowym, a wiedza kiedy i dlaczego ich używać jest bardzo ważna.

Ten artykuł jest krótkim wprowadzeniem do struktury danych trie (wymawianej jako „try”), jej implementacji i analizy złożoności.

Trie

Trie to dyskretna struktura danych, która nie jest dość znana lub szeroko wspominana w typowych kursach algorytmiki, niemniej jednak jest to struktura ważna.

Trie (znane również jako drzewo cyfrowe), a czasami nawet drzewo radixowe lub drzewo prefiksowe (ponieważ można je przeszukiwać po prefiksach), jest uporządkowaną strukturą drzewiastą, która wykorzystuje przechowywane w niej klucze – zazwyczaj ciągi znaków.

Położenie węzła w drzewie definiuje klucz, z którym ten węzeł jest związany, co odróżnia je od drzew wyszukiwania binarnego, w których węzeł przechowuje klucz odpowiadający tylko temu węzłowi.

Wszystkie węzły potomne węzła mają wspólny przedrostek String związany z tym węzłem, podczas gdy korzeń jest związany z pustym String.

Tutaj mamy podgląd TrieNode, którego będziemy używać w naszej implementacji trie:

public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}

Mogą istnieć przypadki, gdy trie jest drzewem wyszukiwania binarnego, ale ogólnie rzecz biorąc, są one różne. Zarówno drzewa wyszukiwania binarnego, jak i try to drzewa, ale każdy węzeł w drzewach wyszukiwania binarnego ma zawsze dwoje dzieci, podczas gdy węzły try mogą mieć ich więcej.

W trie każdy węzeł (z wyjątkiem węzła głównego) przechowuje jeden znak lub cyfrę. Przechodząc przez trie w dół od węzła korzenia do danego węzła n, można utworzyć wspólny prefiks znaków lub cyfr, który jest wspólny także dla innych gałęzi trie.

Przechodząc przez trie w górę od węzła liścia do węzła korzenia, można utworzyć String lub ciąg cyfr.

Tutaj znajduje się klasa Trie, która reprezentuje implementację struktury danych trie:

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

Wspólne operacje

Zobaczmy teraz, jak zaimplementować podstawowe operacje.

3.1. Wstawianie elementów

Pierwszą operacją, którą opiszemy, jest wstawianie nowych węzłów.

Zanim rozpoczniemy implementację, ważne jest, aby zrozumieć algorytm:

1. Ustaw bieżący węzeł jako węzeł główny
2. Ustaw bieżącą literę jako pierwszą literę słowa
3. Jeśli bieżący węzeł ma już istniejące odwołanie do bieżącej litery (poprzez jeden z elementów w polu „children”), to ustaw bieżący węzeł na ten odwołany węzeł. W przeciwnym razie utwórz nowy węzeł, ustaw literę równą bieżącej literze, a także zainicjalizuj bieżący węzeł do tego nowego węzła
4. Powtarzaj krok 3, dopóki klucz nie zostanie przemierzony

Złożoność tej operacji jest O(n), gdzie n reprezentuje rozmiar klucza.

Tutaj znajduje się implementacja tego algorytmu:

public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}

Zobaczmy teraz, jak możemy użyć tej metody do wstawienia nowych elementów do 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;}

Możemy sprawdzić, czy trie zostało już wypełnione nowymi węzłami na podstawie następującego testu:

@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}

3.2. Znajdowanie elementów

Dodajmy teraz metodę sprawdzającą, czy dany element jest już obecny w trie:

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. Jeśli nie jest on obecny nigdzie w trie, to zatrzymaj wyszukiwanie i zwróć false
4. Powtarzaj drugi i trzeci krok, aż w Stringu nie pozostanie żaden znak. Jeśli osiągnięto koniec Stringu, zwróć true

Złożoność tego algorytmu wynosi O(n), gdzie n reprezentuje długość klucza.

Implementacja w języku Java może wyglądać następująco:

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();}

A w działaniu:

@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}

3.3. Usuwanie elementu

Oprócz wstawiania i znajdowania elementu, oczywistym jest, że musimy również mieć możliwość usuwania elementów.

W celu usunięcia elementu musimy wykonać następujące kroki:

1. Sprawdź, czy ten element jest już częścią trie
2. Jeśli element został znaleziony, to usuń go z trie

Złożoność tego algorytmu wynosi O(n), gdzie n reprezentuje długość klucza.

Przyjrzyjmy się szybko implementacji:

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;}

I w działaniu:

@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}

Podsumowanie

W tym artykule zobaczyliśmy krótkie wprowadzenie do struktury danych trie i jej najczęściej wykonywanych operacji oraz ich implementacji.

.