Áttekintés
Az adatszerkezetek fontos eszközt jelentenek a számítógépes programozásban, és nagyon fontos tudni, hogy mikor és miért használjuk őket.
Ez a cikk a trie (ejtsd: “try”) adatszerkezet rövid bemutatása, megvalósítása és komplexitáselemzése.
Trie
A trie egy olyan diszkrét adatszerkezet, amely a tipikus algoritmus-tanfolyamokon nem eléggé ismert vagy széles körben emlegetett, de mégis fontos adatszerkezet.
A trie (más néven digitális fa), sőt néha radixfa vagy prefixfa (mivel prefixek alapján kereshetők), egy rendezett fa szerkezet, amely kihasználja a benne tárolt kulcsokat – általában karakterláncokat.
Egy csomópont pozíciója a fában meghatározza azt a kulcsot, amelyhez az adott csomópont tartozik, ami megkülönbözteti a próbákat a bináris keresőfáktól, amelyekben egy csomópont egy olyan kulcsot tárol, amely csak az adott csomópontnak felel meg.
Egy csomópont minden leszármazottjának közös előtagja az adott csomóponthoz tartozó String, míg a gyökérhez egy üres String tartozik.
Itt van a TrieNode előnézete, amelyet a Trie implementációjában fogunk használni:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Vannak olyan esetek, amikor egy trie egy bináris keresőfa, de általában ezek különböznek. Mind a bináris keresőfák, mind a trie-k fák, de a bináris keresőfák minden csomópontjának mindig két gyermeke van, míg a trie-k csomópontjainak viszont több is lehet.
Egy trie-ben minden csomópont (a gyökércsomópont kivételével) egy karaktert vagy egy számjegyet tárol. A trie-t a gyökércsomóponttól lefelé haladva egy adott n csomópontig, a karakterek vagy számjegyek egy közös előtagja képezhető, amely a trie többi ága számára is közös.
A trie-t egy levélcsomóponttól felfelé haladva a gyökércsomópontig, egy karakterlánc vagy számjegysorozat képezhető.
Itt a Trie osztály, amely a trie adatstruktúra implementációját képviseli:
public class Trie { private TrieNode root; //...}Az általános műveletek
Most nézzük meg, hogyan valósíthatjuk meg az alapvető műveleteket.
3.1. A Trie-osztály a Trie-osztályban található. Elemek beszúrása
Az első művelet, amelyet leírunk, az új csomópontok beszúrása.
Mielőtt elkezdenénk az implementációt, fontos megérteni az algoritmust:
- A jelenlegi csomópontot gyökércsomópontként beállítani
- A jelenlegi betűt a szó első betűjének beállítani
- Ha a jelenlegi csomópontban már létezik hivatkozás a jelenlegi betűre (a “gyerekek” mező egyik elemén keresztül), akkor a jelenlegi csomópontot erre a hivatkozott csomópontra állítsuk. Ellenkező esetben hozzunk létre egy új csomópontot, állítsuk be a betűt az aktuális betűvel egyenlőre, és inicializáljuk az aktuális csomópontot is erre az új csomópontra
- Ismételjük a 3. lépést, amíg a kulcsot be nem járjuk
A művelet bonyolultsága O(n), ahol n a kulcs méretét jelenti.
Itt van ennek az algoritmusnak az implementációja:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Most nézzük meg, hogyan használhatjuk ezt a módszert arra, hogy új elemeket illesszünk be egy trie-be:
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;}Az alábbi tesztből ellenőrizhetjük, hogy a trie-t már feltöltöttük-e új csomópontokkal:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. A trie-t már feltöltöttük. Elemek keresése
Adjunk most hozzá egy módszert, amellyel ellenőrizhetjük, hogy egy adott elem már szerepel-e egy trie-ben:
- Kérdezze meg a gyökér gyermekeit
- Iterálja végig a String minden egyes karakterét
- Vizsgálja meg, hogy az adott karakter már része-e egy al-trie-nek. Ha sehol sincs jelen a trie-ben, akkor állítsuk le a keresést, és adjunk vissza false-t
- Ismételjük meg a második és a harmadik lépést, amíg nem marad egyetlen karakter sem a Stringben. Ha elértük a karakterlánc végét, adjuk vissza a true-t
Az algoritmus bonyolultsága O(n), ahol n a kulcs hosszát jelenti.
A Java implementáció így nézhet ki:
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();}És működés közben:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Elem törlése
Az elem beszúrása és megtalálása mellett nyilvánvaló, hogy az elemek törlésére is képesnek kell lennünk.
A törléshez a következő lépéseket kell követnünk:
- Vizsgáljuk meg, hogy ez az elem már része-e a trie-nek
- Ha az elemet megtaláljuk, akkor töröljük a trie-ból
Az algoritmus bonyolultsága O(n), ahol n a kulcs hosszát jelenti.
Vessünk egy gyors pillantást a megvalósításra:
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;}És működés közben:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Következtetés
Ebben a cikkben röviden bemutattuk a trie adatszerkezetet, annak leggyakoribb műveleteit és azok megvalósítását.