A Trie adatstruktúra a Java-ban

1. Áttekintés

Az adatstruktúrák kulcsfontosságú eszközt jelentenek a számítógépes programozásban, és nagyon fontos tudni, hogy mikor és miért használják őket.

Ez a cikk rövid bemutatást nyújt a trie (ejtsd: „próbáld”) adatszerkezetről, annak megvalósításáról és bonyolultsági elemzéséről.

2. Trie

A trie egy diszkrét adatstruktúra, amely nem túl ismert vagy széles körben emlegetett a tipikus algoritmus tanfolyamokon, de mégis fontos.

A trie (más néven digitális fa), sőt néha radixfa vagy előtagfa (mivel előtagokkal kereshetők) egy rendezett fa szerkezet, amely kihasználja az általa tárolt kulcsokat - általában karakterláncokat.

Egy csomópont helyzete a fában meghatározza azt a kulcsot, amelyhez az adott csomópont társítva van, ami más kísérleteket eredményez, mint a bináris keresési fáké, amelyekben egy csomópont tárol egy kulcsot, amely csak az adott csomópontnak felel meg.

Egy csomópont összes leszármazottjának közös előtagja van a Húr az adott csomóponthoz társítva, míg a gyökér egy üreshez Húr.

Itt van egy előnézetünk TrieNode amelyet felhasználni fogunk a Trie:

nyilvános osztály TrieNode {magán HashMap gyerekek; privát String tartalom; privát logikai isWord; // ...}

Vannak esetek, amikor a trie bináris keresési fa, de általában ezek különböznek. Mind a bináris kereső fák, mind a próbálkozások fák, de a bináris kereső fák mindegyik csomópontjának mindig két gyermeke van, míg a try 'csomópontoknak több lehet.

Egy trie-ben minden csomópont (a gyökércsomópont kivételével) egy karaktert vagy számjegyet tárol. A trie lefelé haladásával a gyökércsomópontról egy adott csomópontra n, kialakítható egy karakterek vagy számjegyek közös előtagja, amelyet a trie más ágai is megosztanak.

Azáltal, hogy egy levélcsomópontról a gyökércsomópontra felfelé halad a trie, a Húr vagy számjegyek sorozata képezhető.

Itt van Trie osztály, amely a trie adatstruktúra megvalósítását jelenti:

nyilvános osztály Trie {private TrieNode gyökér; // ...}

3. Közös műveletek

Most nézzük meg, hogyan lehet végrehajtani az alapvető műveleteket.

3.1. Elemek beszúrása

Az első művelet, amelyet leírunk, új csomópontok beillesztése.

A megvalósítás megkezdése előtt fontos megérteni az algoritmust:

  1. Állítson be egy aktuális csomópontot gyökércsomópontként
  2. Állítsa be az aktuális betűt a szó első betűjeként
  3. Ha az aktuális csomópont már rendelkezik meglévő hivatkozással az aktuális betűre (a „gyermekek” mező egyik elemén keresztül), akkor állítsa az aktuális csomópontot arra a hivatkozott csomópontra. Ellenkező esetben hozzon létre egy új csomópontot, állítsa be a betűt az aktuális betűvel, és inicializálja az aktuális csomópontot is erre az új csomópontra
  4. Ismételje meg a 3. lépést, amíg a kulcs be nem mozdul

Ennek a műveletnek a bonyolultsága az Tovább), hol n a kulcs méretét jelöli.

Itt van ennek az algoritmusnak a megvalósítása:

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 új elemek beszúrására a trie-be:

privát Trie createExampleTrie () {Trie trie = új Trie (); trie.insert ("Programozás"); trie.insert ("is"); trie.insert ("a"); trie.insert ("út"); trie.insert ("of"); trie.insert ("élet"); visszatér trie; }

Megvizsgálhatjuk, hogy a trie-t már új csomópontokkal töltötték fel a következő tesztből:

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

3.2. Elemek keresése

Most adjunk hozzá egy módszert annak ellenőrzésére, hogy egy adott elem szerepel-e már a trie-ben:

  1. Szerezd meg a gyökér gyermekeit
  2. Az egyes karakterek között iterál Húr
  3. Ellenőrizze, hogy ez a karakter már része-e egy sub-trie-nek. Ha a trie-ben sehol nincs, akkor állítsa le a keresést és térjen vissza hamis
  4. Ismételje meg a második és a harmadik lépést, amíg a karakterben nem marad karakter Húr. Ha a Húr elérte, térjen vissza igaz

Ennek az algoritmusnak a bonyolultsága az Tovább), ahol n a kulcs hosszát jelenti.

A Java implementáció a következőképpen nézhet ki:

nyilvános logikai lelet (karakterlánc) {TrieNode current = root; for (int i = 0; i <szó.hossz (); i ++) {char ch = szó.charAt (i); TrieNode csomópont = current.getChildren (). Get (ch); if (csomópont == null) {return false; } current = csomópont; } visszatérő áram.isEndOfWord (); }

És működés közben:

@Test public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements () {Trie trie = createExampleTrie (); assertFalse (trie.containsNode ("3")); assertFalse (trie.containsNode ("vida")); assertTrue (trie.containsNode ("élet")); }

3.3. Elem törlése

Az elem beszúrása és megtalálása mellett nyilvánvaló, hogy képesnek kell lennünk az elemek törlésére is.

A törléshez kövessük a lépéseket:

  1. Ellenőrizze, hogy ez az elem már a trie része-e
  2. Ha az elem megtalálható, akkor távolítsa el a trie-ből

Ennek az algoritmusnak a bonyolultsága az Tovább), ahol n a kulcs hosszát jelenti.

Nézzük meg gyorsan a megvalósítást:

public void delete (karakterlánc szó) {delete (root, word, 0); } privát logikai törlés (TrieNode current, String word, int index) {if (index == word.length ()) {if (! current.isEndOfWord ()) {return false; } current.setEndOfWord (hamis); return current.getChildren (). isEmpty (); } char ch = szó.charAt (index); TrieNode csomópont = current.getChildren (). Get (ch); if (csomópont == null) {return false; } boolean shouldDeleteCurrentNode = delete (csomópont, szó, index + 1) &&! node.isEndOfWord (); if (shouldDeleteCurrentNode) {current.getChildren (). remove (ch); return current.getChildren (). isEmpty (); } return false; }

És működés közben:

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

4. Következtetés

Ebben a cikkben egy rövid bevezetést láthattunk a trie adatszerkezetéről, annak leggyakoribb műveleteiről és azok megvalósításáról.

A cikkben bemutatott példák teljes forráskódja megtalálható a GitHub oldalon.