Structura de date Trie în Java | Baeldung

Vizualizare generală

Structurile de date reprezintă un atu crucial în programarea calculatoarelor, iar a ști când și de ce să le folosești este foarte important.

Acest articol este o scurtă introducere în structura de date Trie (pronunțat „try”), implementarea și analiza complexității acesteia.

Trie

Un trie este o structură de date discretă care nu este destul de bine cunoscută sau menționată pe scară largă în cursurile tipice de algoritmică, dar totuși una importantă.

Un trie (cunoscut și sub numele de arbore digital) și uneori chiar arbore radix sau arbore de prefixe (deoarece pot fi căutate prin prefixe), este o structură arborescentă ordonată, care profită de cheile pe care le stochează – de obicei șiruri de caractere.

Poziția unui nod în arbore definește cheia cu care este asociat acel nod, ceea ce face ca încercările să fie diferite în comparație cu arborii de căutare binară, în care un nod stochează o cheie care corespunde doar acelui nod.

Toți descendenții unui nod au un prefix comun al unui String asociat acelui nod, în timp ce rădăcina este asociată cu un String gol.

Aici avem o previzualizare a TrieNode pe care îl vom folosi în implementarea noastră a Trie:

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

Pot exista cazuri în care o trie este un arbore de căutare binar, dar în general, acestea sunt diferite. Atât arborii de căutare binară, cât și tries sunt arbori, dar fiecare nod din arborii de căutare binară are întotdeauna doi copii, în timp ce nodurile din tries, pe de altă parte, pot avea mai mulți.

Într-un trie, fiecare nod (cu excepția nodului rădăcină) stochează un caracter sau o cifră. Parcurgând trie în jos, de la nodul rădăcină până la un anumit nod n, se poate forma un prefix comun de caractere sau cifre care este împărtășit și de alte ramuri ale trie.

Prin parcurgerea trie în sus, de la un nod frunză la nodul rădăcină, se poate forma un șir de caractere sau o secvență de cifre.

Iată clasa Trie, care reprezintă o implementare a structurii de date Trie:

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

Operații comune

Acum, să vedem cum să implementăm operațiile de bază.

3.1. Inserarea elementelor

Prima operație pe care o vom descrie este inserarea de noi noduri.

Înainte de a începe implementarea, este important să înțelegem algoritmul:

Setați un nod curent ca nod rădăcină
Setați litera curentă ca prima literă a cuvântului
Dacă nodul curent are deja o referință existentă la litera curentă (prin intermediul unuia dintre elementele din câmpul „children”), atunci setați nodul curent la acel nod referit. În caz contrar, se creează un nou nod, se stabilește litera egală cu litera curentă și, de asemenea, se inițializează nodul curent la acest nou nod
Repetați pasul 3 până când cheia este parcursă

Complexitatea acestei operații este O(n), unde n reprezintă dimensiunea cheii.

Iată implementarea acestui algoritm:

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

Acum să vedem cum putem folosi această metodă pentru a insera elemente noi într-o 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;}

Potem testa dacă trie a fost deja populată cu noduri noi din următorul test:

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

3.2. Găsirea elementelor

Să adăugăm acum o metodă pentru a verifica dacă un anumit element este deja prezent într-o trie:

Obțineți copiii rădăcinii
Iterați prin fiecare caracter al șirului
Verificați dacă acel caracter face deja parte dintr-o subtrie. Dacă nu este prezent nicăieri în trie, atunci opriți căutarea și returnați false
Repetați al doilea și al treilea pas până când nu mai există niciun caracter în String. Dacă se ajunge la sfârșitul șirului, se returnează true

Complexitatea acestui algoritm este O(n), unde n reprezintă lungimea cheii.

Implementarea Java poate arăta astfel:

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

Și în acțiune:

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

3.3. Ștergerea unui element

În afară de inserarea și găsirea unui element, este evident că trebuie, de asemenea, să putem șterge elemente.

Pentru procesul de ștergere, trebuie să urmăm pașii:

Verifică dacă acest element face deja parte din trie
Dacă elementul este găsit, atunci îl eliminăm din trie

Complexitatea acestui algoritm este O(n), unde n reprezintă lungimea cheii.

Să aruncăm o privire rapidă asupra implementării:

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