logo

Čo je dátová štruktúra Trie?

Slovo ' Skúste 'je úryvok zo slova' získavanie '. Trie je triedená stromová dátová štruktúra, ktorá ukladá množinu reťazcov. Má počet ukazovateľov rovný počtu znakov abecedy v každom uzle. Dokáže vyhľadať slovo v slovníku pomocou predpony slova. Napríklad, ak predpokladáme, že všetky reťazce sú tvorené písmenami ' a ' až ' S ' v anglickej abecede môže mať každý uzol trie max 26 bodov.

koľko uncí je 10 mililitrov

Trie je tiež známy ako digitálny strom alebo strom predpôn. Poloha uzla v Trie určuje kľúč, s ktorým je tento uzol spojený.

Vlastnosti Trie pre množinu reťazca:

  1. Koreňový uzol trie vždy predstavuje nulový uzol.
  2. Každý potomok uzlov je zoradený abecedne.
  3. Každý uzol môže mať max 26 deti (A až Z).
  4. Každý uzol (okrem koreňa) môže uložiť jedno písmeno abecedy.

Nižšie uvedený diagram znázorňuje ukážkové znázornenie zvončeka, medveďa, vývrtu, pálky, lopty, dorazu, pažby a zásobníka.

Vyskúšajte dátovú štruktúru

Základné operácie Trie

V Trie sú tri operácie:

  1. Vloženie uzla
  2. Hľadanie uzla
  3. Vymazanie uzla

Vloženie uzla do Trie

Prvou operáciou je vloženie nového uzla do trie. Pred začatím implementácie je dôležité pochopiť niektoré body:

  1. Každé písmeno vstupného kľúča (slova) sa vloží ako jednotlivec do Trie_node. Všimnite si, že deti ukazujú na ďalšiu úroveň uzlov Trie.
  2. Pole kľúčových znakov funguje ako index detí.
  3. Ak súčasný uzol už má odkaz na súčasné písmeno, nastavte aktuálny uzol na tento odkazovaný uzol. V opačnom prípade vytvorte nový uzol, nastavte písmeno tak, aby sa rovnalo súčasnému písmenu, a dokonca spustite súčasný uzol s týmto novým uzlom.
  4. Dĺžka znaku určuje hĺbku pokusu.

Implementácia vloženia nového uzla do Trie

 public class Data_Trie { private Node_Trie root; public Data_Trie(){ this.root = new Node_Trie(); } public void insert(String word){ Node_Trie current = root; int length = word.length(); for (int x = 0; x <length; x++){ char l="word.charAt(x);" node_trie node="current.getNode().get(L);" if (node="=" null){ (); current.getnode().put(l, node); } current="node;" current.setword(true); < pre> <h3>Searching a node in Trie</h3> <p>The second operation is to search for a node in a Trie. The searching operation is similar to the insertion operation. The search operation is used to search a key in the trie. The implementation of the searching operation is shown below.</p> <p>Implementation of search a node in the Trie</p> <pre> class Search_Trie { private Node_Trie Prefix_Search(String W) { Node_Trie node = R; for (int x = 0; x <w.length(); x++) { char curletter="W.charAt(x);" if (node.containskey(curletter)) node="node.get(curLetter);" } else return null; node; public boolean search(string w) node_trie !="null" && node.isend(); < pre> <h3>Deletion of a node in the Trie</h3> <p>The Third operation is the deletion of a node in the Trie. Before we begin the implementation, it is important to understand some points:</p> <ol class="points"> <li>If the key is not found in the trie, the delete operation will stop and exit it.</li> <li>If the key is found in the trie, delete it from the trie.</li> </ol> <p> <strong>Implementation of delete a node in the Trie</strong> </p> <pre> public void Node_delete(String W) { Node_delete(R, W, 0); } private boolean Node_delete(Node_Trie current, String W, int Node_index) { if (Node_index == W.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char A = W.charAt(Node_index); Node_Trie node = current.getChildren().get(A); if (node == null) { return false; } boolean Current_Node_Delete = Node_delete(node, W, Node_index + 1) &amp;&amp; !node.isEndOfWord(); if (Current_Node_Delete) { current.getChildren().remove(A); return current.getChildren().isEmpty(); } return false; } </pre> <h2>Applications of Trie</h2> <p> <strong>1. Spell Checker</strong> </p> <p>Spell checking is a three-step process. First, look for that word in a dictionary, generate possible suggestions, and then sort the suggestion words with the desired word at the top.</p> <p>Trie is used to store the word in dictionaries. The spell checker can easily be applied in the most efficient way by searching for words on a data structure. Using trie not only makes it easy to see the word in the dictionary, but it is also simple to build an algorithm to include a collection of relevant words or suggestions.</p> <p> <strong>2. Auto-complete</strong> </p> <p>Auto-complete functionality is widely used on text editors, mobile applications, and the Internet. It provides a simple way to find an alternative word to complete the word for the following reasons.</p> <ul> <li>It provides an alphabetical filter of entries by the key of the node.</li> <li>We trace pointers only to get the node that represents the string entered by the user.</li> <li>As soon as you start typing, it tries to complete your input.</li> </ul> <p> <strong>3. Browser history</strong> </p> <p>It is also used to complete the URL in the browser. The browser keeps a history of the URLs of the websites you&apos;ve visited.</p> <h2>Advantages of Trie</h2> <ol class="points"> <li>It can be insert faster and search the string than hash tables and binary search trees.</li> <li>It provides an alphabetical filter of entries by the key of the node.</li> </ol> <h2>Disadvantages of Trie</h2> <ol class="points"> <li>It requires more memory to store the strings.</li> <li>It is slower than the hash table.</li> </ol> <h2>Complete program in C++</h2> <pre> #include #include #include #define N 26 typedef struct TrieNode TrieNode; struct TrieNode { char info; TrieNode* child[N]; int data; }; TrieNode* trie_make(char info) { TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode)); for (int i = 0; i <n; i++) node → child[i]="NULL;" data="0;" info="info;" return node; } void free_trienode(trienode* node) { for(int i="0;" < n; if (node !="NULL)" free_trienode(node child[i]); else continue; free(node); trie loop start trienode* trie_insert(trienode* flag, char* word) temp="flag;" for (int word[i] ; int idx="(int)" - 'a'; (temp child[idx]="=" null) child[idx]; }trie flag; search_trie(trienode* position="word[i]" child[position]="=" 0; child[position]; && 1) 1; check_divergence(trienode* len="strlen(word);" (len="=" 0) last_index="0;" len; child[position]) j="0;" <n; j++) (j child[j]) + break; last_index; find_longest_prefix(trienode* (!word || word[0]="=" '') null; longest_prefix="(char*)" calloc 1, sizeof(char)); longest_prefix[i]="word[i];" longest_prefix[len]="" branch_idx="check_divergence(flag," longest_prefix) (branch_idx>= 0) { longest_prefix[branch_idx] = &apos;&apos;; longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char)); } return longest_prefix; } int data_node(TrieNode* flag, char* word) { TrieNode* temp = flag; for (int i = 0; word[i]; i++) { int position = (int) word[i] - &apos;a&apos;; if (temp &#x2192; child[position]) { temp = temp &#x2192; child[position]; } } return temp &#x2192; data; } TrieNode* trie_delete(TrieNode* flag, char* word) { if (!flag) return NULL; if (!word || word[0] == &apos;&apos;) return flag; if (!data_node(flag, word)) { return flag; } TrieNode* temp = flag; char* longest_prefix = find_longest_prefix(flag, word); if (longest_prefix[0] == &apos;&apos;) { free(longest_prefix); return flag; } int i; for (i = 0; longest_prefix[i] != &apos;&apos;; i++) { int position = (int) longest_prefix[i] - &apos;a&apos;; if (temp &#x2192; child[position] != NULL) { temp = temp &#x2192; child[position]; } else { free(longest_prefix); return flag; } } int len = strlen(word); for (; i <len; i++) { int position="(int)" word[i] - 'a'; if (temp → child[position]) trienode* rm_node="temp&#x2192;child[position];" temp child[position]="NULL;" free_trienode(rm_node); } free(longest_prefix); return flag; void print_trie(trienode* flag) (!flag) return; printf('%c ', temp→info); for (int i="0;" < n; print_trie(temp child[i]); search(trienode* flag, char* word) printf('search the word %s: word); (search_trie(flag, 0) printf('not found
'); else printf('found!
'); main() flag="trie_make(&apos;&apos;);" 'oh'); 'way'); 'bag'); 'can'); search(flag, 'ohh'); 'ways'); print_trie(flag); printf('
'); printf('deleting 'hello'...
'); 'can'...
'); free_trienode(flag); 0; pre> <p> <strong>Output</strong> </p> <pre> Search the word ohh: Not Found Search the word bag: Found! Search the word can: Found! Search the word ways: Not Found Search the word way: Found! &#x2192; h &#x2192; e &#x2192; l &#x2192; l &#x2192; o &#x2192; w &#x2192; a &#x2192; y &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g &#x2192; c &#x2192; a &#x2192; n deleting the word &apos;hello&apos;... &#x2192; w &#x2192; a &#x2192; y &#x2192; h &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g &#x2192; c &#x2192; a &#x2192; n deleting the word &apos;can&apos;... &#x2192; w &#x2192; a &#x2192; y &#x2192; h &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g </pre> <hr></len;></n;></pre></w.length();></pre></length;>

Aplikácie Trie

1. Kontrola pravopisu

Kontrola pravopisu pozostáva z troch krokov. Najprv vyhľadajte toto slovo v slovníku, vygenerujte možné návrhy a potom zoraďte navrhované slová s požadovaným slovom navrchu.

nahradiť z reťazca v jazyku Java

Trie sa používa na uloženie slova do slovníkov. Kontrola pravopisu sa dá jednoducho použiť najefektívnejším spôsobom vyhľadávaním slov v dátovej štruktúre. Použitie trie nielenže uľahčuje zobrazenie slova v slovníku, ale je tiež jednoduché vytvoriť algoritmus, ktorý obsahuje zbierku relevantných slov alebo návrhov.

previesť z char na int java

2. Automatické dokončovanie

Funkcia automatického dokončovania je široko používaná v textových editoroch, mobilných aplikáciách a na internete. Poskytuje jednoduchý spôsob, ako nájsť alternatívne slovo na dokončenie slova z nasledujúcich dôvodov.

  • Poskytuje abecedný filter záznamov podľa kľúča uzla.
  • Ukazovatele sledujeme len preto, aby sme získali uzol, ktorý predstavuje reťazec zadaný používateľom.
  • Hneď ako začnete písať, pokúsi sa dokončiť váš vstup.

3. História prehliadača

Používa sa tiež na dokončenie adresy URL v prehliadači. Prehliadač uchováva históriu adries URL webových stránok, ktoré ste navštívili.

Výhody Trie

  1. Môže byť vložený rýchlejšie a prehľadávať reťazec ako hašovacie tabuľky a binárne vyhľadávacie stromy.
  2. Poskytuje abecedný filter záznamov podľa kľúča uzla.

Nevýhody Trie

  1. Vyžaduje viac pamäte na uloženie reťazcov.
  2. Je pomalší ako hašovacia tabuľka.

Kompletný program v C++

 #include #include #include #define N 26 typedef struct TrieNode TrieNode; struct TrieNode { char info; TrieNode* child[N]; int data; }; TrieNode* trie_make(char info) { TrieNode* node = (TrieNode*) calloc (1, sizeof(TrieNode)); for (int i = 0; i <n; i++) node → child[i]="NULL;" data="0;" info="info;" return node; } void free_trienode(trienode* node) { for(int i="0;" < n; if (node !="NULL)" free_trienode(node child[i]); else continue; free(node); trie loop start trienode* trie_insert(trienode* flag, char* word) temp="flag;" for (int word[i] ; int idx="(int)" - \'a\'; (temp child[idx]="=" null) child[idx]; }trie flag; search_trie(trienode* position="word[i]" child[position]="=" 0; child[position]; && 1) 1; check_divergence(trienode* len="strlen(word);" (len="=" 0) last_index="0;" len; child[position]) j="0;" <n; j++) (j child[j]) + break; last_index; find_longest_prefix(trienode* (!word || word[0]="=" \'\') null; longest_prefix="(char*)" calloc 1, sizeof(char)); longest_prefix[i]="word[i];" longest_prefix[len]="" branch_idx="check_divergence(flag," longest_prefix) (branch_idx>= 0) { longest_prefix[branch_idx] = &apos;&apos;; longest_prefix = (char*) realloc (longest_prefix, (branch_idx + 1) * sizeof(char)); } return longest_prefix; } int data_node(TrieNode* flag, char* word) { TrieNode* temp = flag; for (int i = 0; word[i]; i++) { int position = (int) word[i] - &apos;a&apos;; if (temp &#x2192; child[position]) { temp = temp &#x2192; child[position]; } } return temp &#x2192; data; } TrieNode* trie_delete(TrieNode* flag, char* word) { if (!flag) return NULL; if (!word || word[0] == &apos;&apos;) return flag; if (!data_node(flag, word)) { return flag; } TrieNode* temp = flag; char* longest_prefix = find_longest_prefix(flag, word); if (longest_prefix[0] == &apos;&apos;) { free(longest_prefix); return flag; } int i; for (i = 0; longest_prefix[i] != &apos;&apos;; i++) { int position = (int) longest_prefix[i] - &apos;a&apos;; if (temp &#x2192; child[position] != NULL) { temp = temp &#x2192; child[position]; } else { free(longest_prefix); return flag; } } int len = strlen(word); for (; i <len; i++) { int position="(int)" word[i] - \'a\'; if (temp → child[position]) trienode* rm_node="temp&#x2192;child[position];" temp child[position]="NULL;" free_trienode(rm_node); } free(longest_prefix); return flag; void print_trie(trienode* flag) (!flag) return; printf(\'%c \', temp→info); for (int i="0;" < n; print_trie(temp child[i]); search(trienode* flag, char* word) printf(\'search the word %s: word); (search_trie(flag, 0) printf(\'not found
\'); else printf(\'found!
\'); main() flag="trie_make(&apos;&apos;);" \'oh\'); \'way\'); \'bag\'); \'can\'); search(flag, \'ohh\'); \'ways\'); print_trie(flag); printf(\'
\'); printf(\'deleting \'hello\'...
\'); \'can\'...
\'); free_trienode(flag); 0; pre> <p> <strong>Output</strong> </p> <pre> Search the word ohh: Not Found Search the word bag: Found! Search the word can: Found! Search the word ways: Not Found Search the word way: Found! &#x2192; h &#x2192; e &#x2192; l &#x2192; l &#x2192; o &#x2192; w &#x2192; a &#x2192; y &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g &#x2192; c &#x2192; a &#x2192; n deleting the word &apos;hello&apos;... &#x2192; w &#x2192; a &#x2192; y &#x2192; h &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g &#x2192; c &#x2192; a &#x2192; n deleting the word &apos;can&apos;... &#x2192; w &#x2192; a &#x2192; y &#x2192; h &#x2192; i &#x2192; t &#x2192; e &#x2192; a &#x2192; b &#x2192; a &#x2192; g </pre> <hr></len;></n;>