Trie-datastrukturen i Java

1. Oversigt

Datastrukturer er et afgørende aktiv i computerprogrammering, og det er meget vigtigt at vide, hvornår og hvorfor de skal bruges.

Denne artikel er en kort introduktion til trie (udtalt "forsøg") datastruktur, dens implementering og kompleksitetsanalyse.

2. Trie

En trie er en diskret datastruktur, der ikke er ganske kendt eller almindeligt nævnt i typiske algoritmekurser, men alligevel en vigtig.

En trie (også kendt som et digitalt træ) og undertiden endda radix-træ eller præfiks-træ (som de kan søges efter præfikser) er en ordnet træstruktur, der udnytter de nøgler, den gemmer - normalt strenge.

En nodes position i træet definerer den nøgle, som noden er tilknyttet, hvilket gør forsøg forskellige i sammenligning med binære søgetræer, hvor en node gemmer en nøgle, der kun svarer til den node.

Alle efterkommere af en node har et fælles præfiks for a Snor tilknyttet den knude, hvorimod roden er forbundet med en tom Snor.

Her har vi en forhåndsvisning af TrieNode som vi vil bruge i vores implementering af programmet Trie:

offentlig klasse TrieNode {private HashMap-børn; privat strengindhold; privat boolsk isWord; // ...}

Der kan være tilfælde, hvor en trie er et binært søgetræ, men generelt er disse forskellige. Både binære søgetræer og forsøg er træer, men hver knude i binære søgetræer har altid to børn, hvorimod forsøgsnoder på den anden side kan have flere.

I en trie lagrer hver node (undtagen rodnoden) et tegn eller et ciffer. Ved at krydse trien ned fra rodnoden til en bestemt node n, kan der dannes et fælles præfiks med tegn eller cifre, som også deles af andre grene af trie.

Ved at krydse trien fra en bladknude til rodknuden, a Snor eller der kan dannes en sekvens af cifre.

Her er Trie klasse, som repræsenterer en implementering af trie datastrukturen:

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

3. Fælles operationer

Lad os nu se, hvordan man implementerer grundlæggende operationer.

3.1. Indsættelse af elementer

Den første operation, som vi beskriver, er indsættelse af nye noder.

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

  1. Indstil en aktuel node som en rodnode
  2. Indstil det aktuelle bogstav som det første bogstav i ordet
  3. Hvis den aktuelle node allerede har en eksisterende henvisning til det aktuelle bogstav (gennem et af elementerne i feltet "børn"), skal du indstille den aktuelle node til den pågældende node. Ellers skal du oprette en ny node, indstille brevet lig med det aktuelle bogstav og initialisere også den aktuelle node til denne nye node
  4. Gentag trin 3, indtil nøglen krydses

Kompleksiteten af ​​denne operation er På), hvor n repræsenterer nøglestørrelsen.

Her er implementeringen af ​​denne algoritme:

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

Lad os nu se, hvordan vi kan bruge denne metode til at indsætte nye elementer i en trie:

privat Trie createExampleTrie () {Trie trie = ny Trie (); trie.insert ("Programmering"); trie.insert ("er"); trie.insert ("a"); trie.insert ("måde"); trie.insert ("af"); trie.insert ("liv"); returtrie; }

Vi kan teste, at trie allerede er blevet befolket med nye noder fra følgende test:

@Test offentligt ugyldigt givenATrie_WhenAddingElements_ThenTrieNotEmpty () {Trie trie = createTrie (); assertFalse (trie.isEmpty ()); }

3.2. Finde elementer

Lad os nu tilføje en metode til at kontrollere, om et bestemt element allerede er til stede i en trie:

  1. Få børn af roden
  2. Iterere gennem hver karakter af Snor
  3. Kontroller, om det tegn allerede er en del af en undertrie. Hvis det ikke findes nogen steder i trien, skal du stoppe søgningen og vende tilbage falsk
  4. Gentag det andet og det tredje trin, indtil der ikke er nogen tegn tilbage i Snor. Hvis afslutningen på Snor er nået, vende tilbage rigtigt

Kompleksiteten af ​​denne algoritme er På), hvor n repræsenterer nøglens længde.

Java-implementering kan se ud:

public boolean find (String word) {TrieNode nuværende = rod; for (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); TrieNode node = current.getChildren (). Get (ch); hvis (node ​​== null) {return false; } nuværende = node; } returner current.isEndOfWord (); }

Og i aktion:

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

3.3. Sletning af et element

Bortset fra at indsætte og finde et element, er det indlysende, at vi også skal være i stand til at slette elementer.

For sletningsprocessen skal vi følge trinene:

  1. Kontroller, om dette element allerede er en del af trien
  2. Hvis elementet findes, skal du fjerne det fra trie

Kompleksiteten af ​​denne algoritme er På), hvor n repræsenterer nøglens længde.

Lad os se hurtigt på implementeringen:

offentlig ugyldig sletning (strengord) {slet (rod, ord, 0); } privat boolsk sletning (TrieNode nuværende, strengord, int-indeks) {if (index == word.length ()) {if (! current.isEndOfWord ()) {return false; } 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 = slet (node, word, index + 1) &&! node.isEndOfWord (); hvis (shouldDeleteCurrentNode) {current.getChildren (). fjern (ch); return current.getChildren (). isEmpty (); } returner falsk; }

Og i aktion:

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

4. Konklusion

I denne artikel har vi set en kort introduktion til trie datastruktur og dens mest almindelige operationer og deres implementering.

Den fulde kildekode til eksemplerne vist i denne artikel kan findes på GitHub.