streamalism.org

1. Prehľad

Dátové štruktúry predstavujú zásadné aktívum v počítačovom programovaní a je veľmi dôležité vedieť, kedy a prečo ich použiť.

Tento článok je krátkym úvodom do trie (vyslovene „vyskúšajte“) dátovej štruktúry, jej implementácie a analýzy zložitosti.

2. Trie

Třída je diskrétna dátová štruktúra, ktorá nie je v typických kurzoch algoritmov celkom známa alebo často spomínaná, ale napriek tomu je dôležitá.

Tri (tiež známy ako digitálny strom) a niekedy dokonca radixový strom alebo strom prefixov (keďže je možné ich vyhľadať podľa predpôn), je usporiadaná stromová štruktúra, ktorá využíva výhody kľúčov, ktoré ukladá - zvyčajne reťazcov.

Poloha uzla v strome definuje kľúč, s ktorým je tento uzol spojený, vďaka čomu sa pokusy líšia v porovnaní s binárnymi vyhľadávacími stromami, v ktorých uzol uchováva kľúč, ktorý zodpovedá iba tomuto uzlu.

Všetci potomkovia uzla majú spoločnú predponu a String spojený s týmto uzlom, zatiaľ čo koreň je spojený s prázdnym String.

Tu máme ukážku z TrieNode ktoré použijeme pri implementácii Trie:

verejná trieda TrieNode {súkromné ​​deti HashMap; súkromný obsah reťazca; private boolean isWord; // ...}

Môžu sa vyskytnúť prípady, keď je trie binárny vyhľadávací strom, ale vo všeobecnosti sú odlišné. Binárne vyhľadávacie stromy aj pokusy sú stromy, ale každý uzol v binárnych vyhľadávacích stromoch má vždy dve deti, zatiaľ čo uzly pokusov môžu mať naopak viac.

V trii je v každom uzle (okrem koreňového) uložený jeden znak alebo číslica. Prejdením trie smerom dole z koreňového uzla do konkrétneho uzla n, môže byť vytvorená spoločná predpona znakov alebo číslic, ktorú zdieľajú aj ďalšie vetvy tri.

Traverzom cez trie z listového uzla do koreňového uzla, a String alebo je možné vytvoriť postupnosť číslic.

Tu je Trie trieda, ktorá predstavuje implementáciu dátovej štruktúry trie:

verejná trieda Trie {súkromný koreň TrieNode; // ...}

3. Spoločné operácie

Teraz sa pozrime, ako implementovať základné operácie.

3.1. Vkladanie prvkov

Prvá operácia, ktorú si popíšeme, je vloženie nových uzlov.

Pred začatím implementácie je dôležité porozumieť algoritmu:

1. Nastaviť aktuálny uzol ako koreňový uzol
2. Nastaví aktuálne písmeno ako prvé písmeno slova
3. Ak má aktuálny uzol už existujúci odkaz na aktuálne písmeno (prostredníctvom jedného z prvkov v poli „deti“), potom nastavte aktuálny uzol na tento odkazovaný uzol. V opačnom prípade vytvorte nový uzol, nastavte písmeno rovnajúce sa aktuálnemu písmenu a tiež inicializujte aktuálny uzol na tento nový uzol
4. Opakujte krok 3, kým sa kľúč neprejde

Zložitosť tejto operácie je O (n), kde n predstavuje veľkosť kľúča.

Tu je implementácia tohto algoritmu:

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

Teraz sa pozrime, ako môžeme touto metódou vložiť nové prvky do triia:

private Trie createExampleTrie () {Trie trie = new Trie (); trie.insert ("Programovanie"); trie.insert ("je"); trie.insert ("a"); trie.insert ("cesta"); trie.insert („of“); trie.insert ("život"); návrat trie; }

Môžeme otestovať, že trie už bolo naplnené novými uzlami z nasledujúceho testu:

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

3.2. Hľadanie prvkov

Teraz pridajme metódu na kontrolu, či je konkrétny prvok už v trii prítomný:

1. Získajte deti z koreňa
2. Iterovať cez každý znak String
3. Skontrolujte, či je tento znak už súčasťou podskupiny. Ak nie je prítomný nikde v trie, zastavte hľadanie a vráťte sa nepravdivé
4. Opakujte druhý a tretí krok, kým v priečinku nezostane žiadny znak String. Ak je koniec String je dosiahnuté, návrat pravda

Zložitosť tohto algoritmu je O (n), kde n predstavuje dĺžku kľúča.

Implementácia Java môže vyzerať takto:

public boolean find (String word) {TrieNode current = root; pre (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); Uzol TrieNode = current.getChildren (). Get (ch); if (node ​​== null) {return false; } aktualne = uzol; } vrátiť current.isEndOfWord (); }

A v akcii:

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

3.3. Odstraňuje sa prvok

Okrem vloženia a nájdenia prvku je zrejmé, že musíme byť tiež schopní vymazať prvky.

V prípade procesu odstránenia musíme postupovať podľa týchto krokov:

1. Skontrolujte, či je tento prvok už súčasťou trie
2. Ak sa prvok nájde, vyberte ho z trie

Zložitosť tohto algoritmu je O (n), kde n predstavuje dĺžku kľúča.

Poďme sa rýchlo pozrieť na implementáciu:

public void delete (Reťazcové slovo) {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); vrátiť current.getChildren (). isEmpty (); } char ch = word.charAt (index); Uzol TrieNode = current.getChildren (). Get (ch); if (node ​​== null) {return false; } boolean shouldDeleteCurrentNode = delete (uzol, slovo, index + 1) &&! node.isEndOfWord (); if (shouldDeleteCurrentNode) {current.getChildren (). remove (ch); vrátiť current.getChildren (). isEmpty (); } return false; }

A v akcii:

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

4. Záver

V tomto článku sme videli krátke predstavenie trie dátovej štruktúry a jej najbežnejších operácií a ich implementácie.

Celý zdrojový kód príkladov uvedených v tomto článku nájdete na GitHub.