logo

Какво е структура от данни Trie?

Думата ' Опитай 'е откъс от думата' извличане '. Trie е сортирана дървовидна структура от данни, която съхранява набор от низове. Той има броя на указателите, равен на броя знаци от азбуката във всеки възел. Може да търси дума в речника с помощта на префикса на думата. Например, ако приемем, че всички низове са формирани от буквите ' а ' да се ' с ' в английската азбука всеки trie възел може да има максимум 26 точки.

абстрактен клас в java

Trie е известен също като цифрово дърво или префиксно дърво. Позицията на възел в Trie определя ключа, с който този възел е свързан.

Свойства на Trie за набор от низа:

  1. Коренният възел на опита винаги представлява нулевия възел.
  2. Всяко дете на възли се сортира по азбучен ред.
  3. Всеки възел може да има максимум 26 деца (А до Я).
  4. Всеки възел (с изключение на корена) може да съхранява една буква от азбуката.

Диаграмата по-долу изобразява представяне на трие за звънец, мече, отвор, бухалка, топка, стоп, приклад и стек.

Опитайте структурата на данните

Основни операции на Trie

Има три операции в Trie:

  1. Вмъкване на възел
  2. Търсене на възел
  3. Изтриване на възел

Вмъкване на възел в Trie

Първата операция е да вмъкнете нов възел в опита. Преди да започнем изпълнението, е важно да разберем някои точки:

  1. Всяка буква от входния ключ (дума) се вмъква като отделна в Trie_node. Имайте предвид, че децата сочат към следващото ниво на Trie възли.
  2. Ключовият масив от символи действа като индекс на деца.
  3. Ако настоящият възел вече има препратка към настоящата буква, задайте настоящия възел към този препратен възел. В противен случай създайте нов възел, задайте буквата да бъде равна на настоящата буква и дори започнете настоящия възел с този нов възел.
  4. Дължината на знака определя дълбочината на опита.

Реализация на вмъкване на нов възел в 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;>

Приложения на Trie

1. Проверка на правописа

Проверката на правописа е процес в три стъпки. Първо потърсете тази дума в речник, генерирайте възможни предложения и след това сортирайте предложените думи с желаната дума в горната част.

сортиране в списък в java

Trie се използва за съхраняване на думата в речници. Проверката на правописа може лесно да се приложи по най-ефективния начин чрез търсене на думи в структура от данни. Използването на trie не само улеснява виждането на думата в речника, но също така е лесно да се изгради алгоритъм, който да включва колекция от подходящи думи или предложения.

2. Автоматично попълване

Функцията за автоматично попълване се използва широко в текстови редактори, мобилни приложения и интернет. Той предоставя лесен начин за намиране на алтернативна дума за завършване на думата поради следните причини.

java филтър поток
  • Той осигурява азбучен филтър на записи по ключа на възела.
  • Проследяваме указатели само за да получим възела, който представлява низа, въведен от потребителя.
  • Веднага щом започнете да пишете, той се опитва да завърши въвеждането ви.

3. История на браузъра

Използва се и за попълване на URL адреса в браузъра. Браузърът пази история на URL адресите на уебсайтовете, които сте посетили.

Предимства на Trie

  1. Може да се вмъкне по-бързо и да се търси в низа от хеш таблиците и двоичните дървета за търсене.
  2. Той осигурява азбучен филтър на записи по ключа на възела.

Недостатъци на Trie

  1. Изисква повече памет за съхраняване на низовете.
  2. Тя е по-бавна от хеш-таблицата.

Пълна програма на 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;>