Datová struktura Trie v Javě | Baeldung

Přehled

Datové struktury představují zásadní přínos v počítačovém programování a je velmi důležité vědět, kdy a proč je použít.

Tento článek je stručným úvodem do datové struktury trie (vyslovuje se „try“), její implementace a analýzy složitosti.

Trie

Trie je diskrétní datová struktura, která není v typických kurzech algoritmizace úplně známá nebo hojně zmiňovaná, ale přesto je důležitá.

Trie (známé také jako digitální strom) a někdy i radixový strom nebo prefixový strom (protože je lze prohledávat pomocí prefixů), je uspořádaná stromová struktura, která využívá klíče, které uchovává – obvykle řetězce.

Pozice uzlu ve stromu určuje klíč, s nímž je daný uzel spojen, čímž se tries liší ve srovnání s binárními vyhledávacími stromy, v nichž uzel uchovává klíč, který odpovídá pouze tomuto uzlu.

Všichni potomci uzlu mají společný prefix řetězce asociovaného s tímto uzlem, zatímco kořen je asociován s prázdným řetězcem.

Tady máme náhled TrieNode, který budeme používat v naší implementaci Trie:

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

Mohou nastat případy, kdy je trie binárním vyhledávacím stromem, ale obecně jsou tyto případy jiné. Jak binární vyhledávací stromy, tak trie jsou stromy, ale každý uzel binárního vyhledávacího stromu má vždy dva potomky, zatímco uzly trie jich naopak mohou mít více.

V trie je v každém uzlu (kromě kořenového) uložen jeden znak nebo číslice. Procházením tria směrem dolů od kořenového uzlu ke konkrétnímu uzlu n lze vytvořit společnou předponu znaků nebo číslic, kterou sdílejí i ostatní větve tria.

Procházením tria směrem nahoru od listového uzlu ke kořenovému uzlu lze vytvořit řetězec nebo posloupnost číslic.

Tady je třída Trie, která představuje implementaci datové struktury trie:

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

Obvyklé operace

Nyní se podíváme na to, jak implementovat základní operace.

3.1. Vkládání prvků

První operací, kterou si popíšeme, je vkládání nových uzlů.

Než začneme s implementací, je důležité pochopit algoritmus:

Nastavit aktuální uzel jako kořenový uzel
Nastavit aktuální písmeno jako první písmeno slova
Pokud má aktuální uzel již existující odkaz na aktuální písmeno (prostřednictvím některého z prvků v poli „děti“), pak nastavte aktuální uzel na tento odkazovaný uzel. V opačném případě vytvořte nový uzel, nastavte písmeno rovné aktuálnímu písmenu a rovněž inicializujte aktuální uzel na tento nový uzel
Krok 3 opakujte, dokud není klíč procházen

Složitost této operace je O(n), kde n představuje velikost klíče.

Tady je implementace tohoto algoritmu:

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

Nyní se podíváme, jak můžeme tuto metodu použít k vložení nových prvků 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;}

To, že trie již bylo naplněno novými uzly, můžeme otestovat z následujícího testu:

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

3.2. Vyhledávání prvků

Přidáme nyní metodu pro kontrolu, zda se konkrétní prvek již v trie nachází:

Zjistit děti kořene
Protočit každý znak řetězce
Zkontrolovat, zda je tento znak již součástí dílčího trie. Pokud se nikde v trie nevyskytuje, zastav hledání a vrať false
Pak opakuj druhý a třetí krok, dokud v řetězci nezůstane žádný znak. Pokud je dosaženo konce řetězce, vraťte true

Složitost tohoto algoritmu je O(n), kde n představuje délku klíče.

Implementace v jazyce Java může vypadat takto:

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 v akci:

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

3.3. Odstranění prvku

Kromě vložení a nalezení prvku je zřejmé, že potřebujeme umět prvky také odstranit.

Při mazání musíme postupovat takto:

Zkontrolovat, zda je tento prvek již součástí tria
Pokud je prvek nalezen, pak jej z tria odstraníme

Složitost tohoto algoritmu je O(n), kde n představuje délku klíče.

Podívejme se na implementaci:

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