logo

Što je struktura podataka Trie?

Riječ ' Pokušaj ' je izvadak iz riječi ' dohvaćanje '. Trie je sortirana podatkovna struktura temeljena na stablu koja pohranjuje skup nizova. Ima broj pokazivača jednak broju znakova abecede u svakom čvoru. Može pretraživati ​​riječ u rječniku uz pomoć prefiksa riječi. Na primjer, ako pretpostavimo da su svi nizovi sastavljeni od slova ' a 'do' S ' u engleskoj abecedi, svaki trie čvor može imati najviše 26 bodova.

liste od lateksa

Trie je također poznat kao digitalno stablo ili stablo prefiksa. Položaj čvora u Trie određuje ključ s kojim je taj čvor povezan.

Svojstva Trie za skup niza:

  1. Korijenski čvor trie uvijek predstavlja nulti čvor.
  2. Svako dijete čvorova sortirano je abecednim redom.
  3. Svaki čvor može imati najviše 26 djeca (A do Ž).
  4. Svaki čvor (osim korijena) može pohraniti jedno slovo abecede.

Donji dijagram prikazuje trie prikaz za zvono, medvjedić, otvor, palicu, loptu, stop, kundak i hrpu.

Isprobajte strukturu podataka

Osnovne operacije Trie

Postoje tri operacije u Trie:

  1. Umetanje čvora
  2. Pretraživanje čvora
  3. Brisanje čvora

Umetanje čvora u Trie

Prva operacija je umetanje novog čvora u trie. Prije nego što započnemo implementaciju, važno je razumjeti neke točke:

  1. Svako slovo ulaznog ključa (riječi) umetnuto je kao pojedinac u Trie_node. Imajte na umu da djeca pokazuju na sljedeću razinu Trie čvorova.
  2. Niz ključnih znakova djeluje kao indeks djece.
  3. Ako sadašnji čvor već ima referencu na sadašnje slovo, postavite sadašnji čvor na taj referencirani čvor. U suprotnom, stvorite novi čvor, postavite slovo da bude jednako sadašnjem slovu, pa čak i započnite sadašnji čvor s ovim novim čvorom.
  4. Duljina znaka određuje dubinu pokušaja.

Implementacija umetanja novog čvora u 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;>

Prijave Trie

1. Provjera pravopisa

Provjera pravopisa je proces u tri koraka. Najprije potražite tu riječ u rječniku, generirajte moguće prijedloge, a zatim poredajte prijedloge riječi sa željenom riječi na vrhu.

python popis inicijalizirati

Trie se koristi za pohranjivanje riječi u rječnike. Provjera pravopisa može se jednostavno primijeniti na najučinkovitiji način traženjem riječi u strukturi podataka. Korištenje trie ne samo da olakšava vidjeti riječ u rječniku, već je također jednostavno izgraditi algoritam za uključivanje zbirke relevantnih riječi ili prijedloga.

2. Automatsko dovršavanje

javascript komentar

Funkcija automatskog dovršavanja naširoko se koristi u uređivačima teksta, mobilnim aplikacijama i internetu. Omogućuje jednostavan način pronalaženja alternativne riječi za dovršetak riječi iz sljedećih razloga.

  • Omogućuje abecedni filtar unosa prema ključu čvora.
  • Pokazivače pratimo samo da bismo dobili čvor koji predstavlja niz koji je unio korisnik.
  • Čim počnete tipkati, pokušava dovršiti vaš unos.

3. Povijest preglednika

Također se koristi za dovršavanje URL-a u pregledniku. Preglednik čuva povijest URL-ova web stranica koje ste posjetili.

Prednosti Trie

  1. Može se umetnuti brže i pretraživati ​​niz od hash tablica i stabala binarnog pretraživanja.
  2. Omogućuje abecedni filtar unosa prema ključu čvora.

Nedostaci Trie

  1. Za pohranjivanje nizova potrebno je više memorije.
  2. Sporiji je od hash tablice.

Kompletan program u 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;>