Trie-datastrukturen i Java

1. Oversikt

Datastrukturer er en viktig ressurs i dataprogrammering, og det er veldig viktig å vite når og hvorfor de skal brukes.

Denne artikkelen er en kort introduksjon til trie (uttalt "prøve") datastruktur, implementering og kompleksitetsanalyse.

2. Trie

En trie er en diskret datastruktur som ikke er veldig kjent eller nevnt i typiske algoritmekurs, men likevel en viktig.

En trie (også kjent som et digitalt tre) og noen ganger til og med radiks-treet eller prefiks-treet (som det kan søkes etter prefikser), er en ordnet trestruktur, som utnytter nøklene den lagrer - vanligvis strenger.

En nodes posisjon i treet definerer nøkkelen som noden er assosiert med, noe som gjør prøver forskjellige i forhold til binære søketrær, der en node lagrer en nøkkel som bare tilsvarer den noden.

Alle etterkommere av en node har et felles prefiks av a String assosiert med den noden, mens roten er assosiert med en tom String.

Her har vi en forhåndsvisning av TrieNode som vi skal bruke i implementeringen av Trie:

offentlig klasse TrieNode {private HashMap-barn; privat strenginnhold; privat boolsk isWord; // ...}

Det kan være tilfeller når en trie er et binært søketre, men generelt er disse forskjellige. Både binære søketrær og prøver er trær, men hver node i binære søketrær har alltid to barn, mens forsøksnoder derimot kan ha flere.

I en trie lagrer hver node (unntatt rotnoden) ett tegn eller et siffer. Ved å krysse trien ned fra rotnoden til en bestemt node n, kan det dannes et vanlig prefiks med tegn eller sifre som også deles av andre grener av trie.

Ved å krysse opp trien fra en bladnode til rotnoden, a String eller en sekvens av sifre kan dannes.

Her er Trie klasse, som representerer en implementering av trie datastrukturen:

offentlig klasse Trie {privat TrieNode-rot; // ...}

3. Vanlige operasjoner

La oss nå se hvordan du implementerer grunnleggende operasjoner.

3.1. Sette inn elementer

Den første operasjonen vi skal beskrive er innsetting av nye noder.

Før vi starter implementeringen, er det viktig å forstå algoritmen:

  1. Sett en nåværende node som en rotnode
  2. Sett gjeldende bokstav som første bokstav i ordet
  3. Hvis den nåværende noden allerede har en eksisterende referanse til gjeldende bokstav (gjennom ett av elementene i "barn" -feltet), må du sette gjeldende node til den refererte noden. Ellers oppretter du en ny node, setter bokstaven lik gjeldende bokstav, og initialiserer også gjeldende node til denne nye noden
  4. Gjenta trinn 3 til nøkkelen krysses

Kompleksiteten i denne operasjonen er På), hvor n representerer nøkkelstørrelsen.

Her er implementeringen av denne algoritmen:

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

La oss nå se hvordan vi kan bruke denne metoden til å sette inn nye elementer i en trie:

privat Trie createExampleTrie () {Trie trie = ny Trie (); trie.insert ("Programmering"); trie.insert ("er"); trie.insert ("a"); trie.insert ("måte"); trie.insert ("of"); trie.insert ("liv"); retur trie; }

Vi kan teste at trie allerede har blitt fylt med nye noder fra følgende test:

@Test offentlig ugyldig givenATrie_WhenAddingElements_ThenTrieNotEmpty () {Trie trie = createTrie (); assertFalse (trie.isEmpty ()); }

3.2. Finne elementer

La oss nå legge til en metode for å sjekke om et bestemt element allerede er til stede i en trie:

  1. Få barn av roten
  2. Iterer gjennom hver karakter av String
  3. Sjekk om denne karakteren allerede er en del av en undergruppe. Hvis den ikke er til stede noe sted i trien, så stopp søket og gå tilbake falsk
  4. Gjenta det andre og det tredje trinnet til det ikke er noen tegn igjen i String. Hvis slutten av String er nådd, tilbake ekte

Kompleksiteten til denne algoritmen er På), hvor n representerer lengden på nøkkelen.

Java-implementering kan se ut:

offentlig boolsk funn (strengord) {TrieNode gjeldende = rot; for (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); TrieNode node = current.getChildren (). Get (ch); hvis (node ​​== null) {return false; } gjeldende = node; } returner gjeldende.isEndOfWord (); }

Og i aksjon:

@Test offentlig ugyldig givenATrie_WhenAddingElements_ThenTrieContainsThoseElements () {Trie trie = createExampleTrie (); assertFalse (trie.containsNode ("3")); assertFalse (trie.containsNode ("vida")); assertTrue (trie.containsNode ("liv")); }

3.3. Slette et element

Bortsett fra å sette inn og finne et element, er det åpenbart at vi også trenger å kunne slette elementer.

For slettingsprosessen må vi følge trinnene:

  1. Sjekk om dette elementet allerede er en del av trien
  2. Hvis elementet er funnet, så fjern det fra trie

Kompleksiteten til denne algoritmen er På), hvor n representerer lengden på nøkkelen.

La oss se raskt på implementeringen:

sletting av offentlig tomrom (strengord) {slett (rot, ord, 0); } privat boolsk sletting (TrieNode gjeldende, strengord, int-indeks) {if (indeks == ord.lengde ()) {hvis (! gjeldende.isEndOfWord ()) {return falsk; } current.setEndOfWord (false); return current.getChildren (). isEmpty (); } char ch = word.charAt (indeks); TrieNode node = current.getChildren (). Get (ch); hvis (node ​​== null) {return false; } boolsk shouldDeleteCurrentNode = slett (node, word, index + 1) &&! node.isEndOfWord (); hvis (shouldDeleteCurrentNode) {current.getChildren (). fjern (ch); return current.getChildren (). isEmpty (); } returner falsk; }

Og i aksjon:

@Test ugyldig nårDeletingElements_ThenTreeDoesNotContainThoseElements () {Trie trie = createTrie (); assertTrue (trie.containsNode ("Programmering")); trie.delete ("Programmering"); assertFalse (trie.containsNode ("Programmering")); }

4. Konklusjon

I denne artikkelen har vi sett en kort introduksjon til trie datastruktur og dens vanligste operasjoner og implementering av dem.

Den fullstendige kildekoden for eksemplene vist i denne artikkelen finner du på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found