streamalism.org

1. Pregled

Strukture podataka predstavljaju presudnu prednost u računalnom programiranju, a vrlo je važno znati kada i zašto ih koristiti.

Ovaj je članak kratki uvod u trie (izgovara se "try") strukturu podataka, njezinu provedbu i analizu složenosti.

2. Trie

Trie je diskretna struktura podataka koja nije sasvim poznata ili široko spominjana u tipičnim tečajevima algoritama, ali unatoč tome važna.

Trie (poznato i kao digitalno stablo), a ponekad čak i stablo radixa ili stablo prefiksa (jer ih se može pretraživati ​​po prefiksima), uređena je struktura stabla koja koristi ključeve koje pohranjuje - obično nizove.

Položaj čvora u stablu definira ključ s kojim je taj čvor povezan, što čini pokušaje drugačijima u usporedbi s binarnim stablima pretraživanja, u kojem čvor čuva ključ koji odgovara samo tom čvoru.

Svi potomci čvora imaju zajednički prefiks a Niz povezan s tim čvorom, dok je korijen povezan s praznim Niz.

Ovdje imamo pregled TrieNode koje ćemo koristiti u provedbi Trie:

javni razred TrieNode {privatna djeca HashMap-a; privatni sadržaj niza; privatni logički isWord; // ...}

Mogu biti slučajevi kada je trie binarno stablo pretraživanja, ali općenito su to različiti. I stabla binarnog pretraživanja i pokušaji su stabla, ali svaki čvor u binarnim stablima pretraživanja uvijek ima dvoje djece, dok čvorovi pokušaja, s druge strane, mogu imati više.

U trieu svaki čvor (osim korijenskog) pohranjuje jedan znak ili znamenku. Prelaskom trie od korijenskog čvora do određenog čvora n, može se oblikovati zajednički prefiks znakova ili znamenki koji dijele i druge grane trija.

Prelaskom gore trie od lisnog čvora do korijenskog čvora, a Niz ili se može stvoriti slijed znamenki.

Ovdje je Trie klasa, koja predstavlja implementaciju trie strukture podataka:

javna klasa Trie {privatni korijen TrieNode; // ...}

3. Zajedničke operacije

Sada, da vidimo kako implementirati osnovne operacije.

3.1. Umetanje elemenata

Prva operacija koju ćemo opisati je umetanje novih čvorova.

Prije nego započnemo s implementacijom, važno je razumjeti algoritam:

1. Postavite trenutni čvor kao korijenski čvor
2. Postavite trenutačno slovo kao prvo slovo riječi
3. Ako trenutni čvor već postoji referenca na trenutno slovo (kroz jedan od elemenata u polju "djeca"), tada postavite trenutni čvor na taj referencirani čvor. U suprotnom, stvorite novi čvor, postavite slovo jednako trenutnom slovu, a također inicijalizirajte trenutni čvor na taj novi čvor
4. Ponavljajte korak 3 dok se tipka ne prebaci

Složenost ove operacije je Na), gdje n predstavlja veličinu ključa.

Evo implementacije ovog algoritma:

javni prazan umetak (niz riječi) {TrieNode current = root; za (char l: word.toCharArray ()) {current = current.getChildren (). computeIfAbsent (l, c -> new TrieNode ()); } current.setEndOfWord (true); }

Sada da vidimo kako možemo koristiti ovu metodu za umetanje novih elemenata u trie:

private Trie createExampleTrie () {Trie trie = new Trie (); trie.insert ("Programiranje"); trie.insert ("je"); trie.insert ("a"); trie.insert ("put"); trie.insert ("od"); trie.insert ("život"); povratak trie; }

Možemo testirati da je trie već popunjeno novim čvorovima iz sljedećeg testa:

@Test javna praznina givenATrie_WhenAddingElements_ThenTrieNotEmpty () {Trie trie = createTrie (); assertFalse (trie.isEmpty ()); }

3.2. Pronalaženje elemenata

Dodajmo sada metodu za provjeru je li određeni element već prisutan u trie:

1. Nabavite djecu korijena
2. Ponavljajte kroz svaki lik Niz
3. Provjerite je li taj lik već dio potknjiga. Ako ga nema nigdje u trieu, zaustavite potragu i vratite se lažno
4. Ponavljajte drugi i treći korak dok u znaku ne ostane nijedan znak Niz. Ako je kraj Niz je postignuto, povratak pravi

Složenost ovog algoritma je Na), gdje n predstavlja duljinu ključa.

Implementacija Jave može izgledati ovako:

javno logičko pronalaženje (riječ u nizu) {TrieNode current = root; for (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); Čvor TrieNode = current.getChildren (). Get (ch); if (node ​​== null) {return false; } trenutni = čvor; } vratiti current.isEndOfWord (); }

I na djelu:

@Test javna praznina givenATrie_WhenAddingElements_ThenTrieContainsThoseElements () {Trie trie = createExampleTrie (); assertFalse (trie.contensNode ("3")); assertFalse (trie.containsNode ("vida")); assertTrue (trie.containsNode ("život")); }

3.3. Brisanje elementa

Osim umetanja i pronalaska elementa, očito je da moramo biti u mogućnosti i brisati elemente.

Za postupak brisanja moramo slijediti korake:

1. Provjerite je li ovaj element već dio trie
2. Ako je element pronađen, uklonite ga iz trie

Složenost ovog algoritma je Na), gdje n predstavlja duljinu ključa.

Kratko ćemo pogledati implementaciju:

public void delete (String word) {delete (korijen, riječ, 0); } privatno logičko brisanje (TrieNode current, String word, int index) {if (index == word.length ()) {if (! current.isEndOfWord ()) {return false; } current.setEndOfWord (false); vrati current.getChildren (). isEmpty (); } char ch = word.charAt (indeks); Čvor TrieNode = current.getChildren (). Get (ch); if (node ​​== null) {return false; } boolean shouldDeleteCurrentNode = delete (node, word, index + 1) &&! node.isEndOfWord (); if (shouldDeleteCurrentNode) {current.getChildren (). remove (ch); vrati current.getChildren (). isEmpty (); } return false; }

I na djelu:

@Test void whenDeletingElements_ThenTreeDoesNotContainThoseElements () {Trie trie = createTrie (); assertTrue (trie.containsNode ("Programiranje")); trie.delete ("Programiranje"); assertFalse (trie.containsNode ("Programiranje")); }

4. Zaključak

U ovom smo članku vidjeli kratki uvod u strukturu podataka trie i njegove najčešće operacije i njihovu implementaciju.

Cjeloviti izvorni kod za primjere prikazane u ovom članku možete pronaći na GitHubu.