Trie datastruktur i Java | Baeldung

Översikt

Datastrukturer är en viktig tillgång inom dataprogrammering, och det är mycket viktigt att veta när och varför man ska använda dem.

Den här artikeln är en kortfattad introduktion till trie-datastrukturen (som uttalas ”try”), dess implementering och komplexitetsanalys.

Trie

En trie är en diskret datastruktur som inte är helt välkänd eller allmänt omnämnd i typiska algoritmkurser, men som ändå är viktig.

En trie (även känd som ett digitalt träd) och ibland till och med radixträd eller prefixträd (eftersom de kan sökas med hjälp av prefix), är en ordnad trädstruktur som drar nytta av de nycklar som den lagrar – vanligtvis strängar.

En nods position i trädet definierar den nyckel som noden är associerad med, vilket gör tries annorlunda jämfört med binära sökträd, där en nod lagrar en nyckel som endast motsvarar den noden.

Alla efterkommande till en nod har ett gemensamt prefix av en sträng som är associerad med den noden, medan roten är associerad med en tom sträng.

Här har vi en förhandsgranskning av TrieNode som vi kommer att använda i vår implementering av Trie:

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

Det kan förekomma fall då en Trie är ett binärt sökträd, men generellt sett är dessa olika. Både binära sökträd och tries är träd, men varje nod i binära sökträd har alltid två barn, medan tries noder å andra sidan kan ha fler.

I en trie lagrar varje nod (utom rotnoden) ett tecken eller en siffra. Genom att traversera trian nedåt från rotnoden till en viss nod n kan ett gemensamt prefix av tecken eller siffror bildas som även delas av andra grenar av trian.

Genom att traversera uppåt i trian från en bladnod till rotnoden kan en sträng eller en sekvens av siffror bildas.

Här är Trie-klassen, som representerar en implementering av trie-datastrukturen:

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

Gemensamma operationer

Nu ska vi se hur man implementerar grundläggande operationer.

3.1. Infoga element

Den första operationen som vi ska beskriva är infogandet av nya noder.

Innan vi börjar implementeringen är det viktigt att förstå algoritmen:

Sätt en aktuell nod som rotnod
Sätt den aktuella bokstaven som ordets första bokstav
Om den aktuella noden redan har en befintlig referens till den aktuella bokstaven (genom ett av elementen i fältet ”children”), sätts då aktuell nod till den refererade noden. Annars skapar du en ny nod, sätter bokstaven lika med den aktuella bokstaven och initialiserar även aktuell nod till denna nya nod
Upprepa steg 3 tills nyckeln genomkorsats

Komplexiteten för denna operation är O(n), där n representerar nyckelstorleken.

Här är implementeringen av denna 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);}

Nu ska vi se hur vi kan använda denna metod för att infoga nya element i en 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;}

Vi kan testa att trie redan har fyllts med nya noder från följande test:

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

3.2. Hitta element

Låt oss nu lägga till en metod för att kontrollera om ett visst element redan finns i en trie:

Hämta barn till roten
Iterera genom varje tecken i strängen
Kontrollera om det tecknet redan är en del av en undertrie. Om det inte finns någonstans i trie, stoppa då sökningen och återge false
Upprepa det andra och det tredje steget tills det inte finns något tecken kvar i strängen. Om slutet av strängen nås, returnera true

Komplexiteten för denna algoritm är O(n), där n representerar längden på nyckeln.

Javaimplementationen kan se ut så här:

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

Och i praktiken:

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

3.3. Radering av ett element

Sutom att infoga och hitta ett element är det uppenbart att vi också måste kunna radera element.

För raderingsprocessen måste vi följa stegen:

Kontrollera om det här elementet redan är en del av triangeln
Om elementet hittas, ta då bort det från triangeln

Komplexiteten för den här algoritmen är O(n), där n representerar längden på nyckeln.

Låt oss ta en snabb titt på genomförandet:

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