Title Trie.pdf ✅

N-ary Tree - Trie Topics 1. Introduction to Trie 2. What do we mean by ‘Trie’? 3. Implementation of Trie 4. Time Complexity 5. Space Complexity 6. Problems & Solutions 7. Important References
Introduction Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). If we store keys in a binary search tree, a well balanced BST will need time proportional to M ✕ log2 (N), where M is maximum string length and N is number of keys in the tree. Using trie, we can search for the key in O(M) time. There are many algorithms and data structures to index and search strings inside a text, some of them are included in the standard libraries, but not all of them; the trie data structure is a good example of one that isn’t. Let word be a single string and let dictionary be a large set of words. If we have a dictionary, and we need to know if a single word is present in the dictionary, trie is the data structure that can help us. But you may be asking yourself, “Why use tries if hash tables can do the same?” There are two main reasons: 1. The tries can insert and find strings in O(L) time (where L represents the length of a single word). This is a bit faster than a hash table. 2. Hash tables can only find for the word in a dictionary of words that match exactly with the single word that we are trying to find; however the trie allows us to find words that have a single character different, a prefix in common, a character missing, etc. For example, consider a web browser. Do you know how the web browser can auto complete your text or show you many possibilities of the text that you could be writing? Yes, with the help of trie you can do it in a very quick method. Do you know how an orthographic corrector can check that every word that you type is in a dictionary? Again a trie. You can also use a trie for suggestions on corrections of the words that are present in the text but not in the dictionary. What do we mean by ‘Trie’? You may read about how wonderful the tries are, but maybe you don’t know yet what the tries are and why the tries have this name. The word trie is an infix of the word “retrieval” because the trie can find a single word in a dictionary with only a prefix of the word. The main idea of the trie data structure consists of the following parts: 1. The trie is a tree where each vertex represents a single word or a prefix. 2. The root represents an empty string (“”), the vertices that are direct sons of the root represent prefixes of length 1, the vertices that are 2 edges of distance from the root represent prefixes of length 2, the vertices that are 3 edges of distance from the root represent prefixes of length 3 and so on. In other words, a vertex that is k edges of distance from the root has an associated prefix of length k. 3. Let v and w be two vertices of the trie, and assume that v is a direct father of w, then v must have an associated prefix of w.