Trie Data Structure

This slide contains full description about a Data Structure Called Trie Data Structure. A common example of an Application which use trie data structure to store data is dictionary. The basic operations like Adding, Deleting, Searching etc are included in the slide.

1. CSE 225 DATA STRUCTURE & ALGORITHM PROJECT PRESENTATION Group Members: Arifur Rahman Badiuzzaman Pranto Tasnova Nusrat Akila Rahman TRIE

2. What Is TRIE? Trie is an efficient information retrieval data structure also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store A dynamic set or associative array where the keys are usually strings.

3. Why Trie Data Structure? Searching trees in general favor keys which are of fixed size since this leads to efficient storage management. However in case of applications which are retrieval based and which call for keys varying length, tries provide better options. Tries are also called as Lexicographic Search trees. The name trie (pronounced as “try”)originated from the word “ retrieval ”.

4. EXAMPLE:- A trie for keys A, to, tea, ted, ten, i , in & inn

5. NODE STRUCTURE private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap<> (); endOfWord = false ; } } Initializing a map with key & value named children Indicates Whether This Node Completes A Word

6. INSERTION

7. INSERTION ALGORITHM TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } root { } False

8. INSERTION ALGORITHM False False False root False False False d a t a False False False False True e m o True s False False True b a TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba fALSE {} FALSE cs C? c S True cse S? e? e data d? d a ? t ? a? True True

9. Insert: cs False False root c a insert (“CS”) public class Trie { public Trie () { root = new TrieNode (); } Private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false; } } public void insert (String word) { insertRecursive (root, word, 0); } private void insertRecursive ( TrieNode current, String word, int index) { if (index == word.length ()) { current.endOfWord = true ; return ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null ) { node = new TrieNode (); current.children.put ( ch , node); } insertRecursive (node, word, index + 1); } Public static void main(String [] args ){ Trie tree = new Trie (); tree.insert (“CS”) } insertRecursiver (root,“CS”,0)

10. Insert: cs False False root C a public class Trie { public Trie () { root = new TrieNode (); } Private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false; } } public void insert (String word) { insertRecursive (root, word, 0); } private void insertRecursive ( TrieNode current, String word, int index) { if (index == word.length ()) { current.endOfWord = true ; return ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null ) { node = new TrieNode (); current.children.put ( ch , node); } insertRecursive (node, word, index + 1); } Public static void main(String [] args ){ Trie tree = new Trie (); tree.insert (“CS”) } insertRecursiver (root,“CS”,0) insertRecursiver (root,“CS”,1) Insert(“CS”) False S insertRecursiver (root,“CS”,2)

11. Insert: cs False False root C public class Trie { public Trie () { root = new TrieNode (); } Private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false; } } public void insert (String word) { insertRecursive (root, word, 0); } private void insertRecursive ( TrieNode current, String word, int index) { if (index == word.length ()) { current.endOfWord = true ; return ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null ) { node = new TrieNode (); current.children.put ( ch , node); } insertRecursive (node, word, index + 1); } Public static void main(String [] args ){ Trie tree = new Trie (); tree.insert (“CS”) } insertRecursiver (root,“CS”,0) insertRecursiver (root,“CS”,1) Insert(“CS”) S insertRecursiver (root,“CS”,2) True False True

12. Insert: cse C False s False False root True a True e public class Trie { public Trie () { root = new TrieNode (); } Private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false; } } public void insert (String word) { insertRecursive (root, word, 0); } private void insertRecursive ( TrieNode current, String word, int index) { if (index == word.length ()) { current.endOfWord = true ; return ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null ) { node = new TrieNode (); current.children.put ( ch , node); } insertRecursive (node, word, index + 1); } True

13. Insert: data C False s False e True True root False False False d a t a False m public class Trie { public Trie () { root = new TrieNode (); } Private class TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; public TrieNode () { children = new HashMap <>(); endOfWord = false; } } public void insert (String word) { insertRecursive (root, word, 0); } private void insertRecursive ( TrieNode current, String word, int index) { if (index == word.length ()) { current.endOfWord = true ; return ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null ) { node = new TrieNode (); current.children.put ( ch , node); } insertRecursive (node, word, index + 1); } True

14. INSERTION ALGORITHM Insert: demo C False s False e True True root False False False d a t a True False False False True e m o s TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba

15. INSERTION ALGORITHM Insert: bba C False s False e True True root False False False d a t a True False False False True e m o True s b False False True b a TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba

16. TIME COMPLEXITY Average Length of word = l Number of word = n Time Complexity Of Insertion : O( l * n )

17. SEARCHING

18. SEARCHING ALGORITHM Search: bba C False s False e True True root False False False d a t a True False False False True e m o True s b False False True b a TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba true b ? b ? a? True? bba is found in the trie YES!

19. SEARCHING ALGORITHM Search: csse C False s False e True True root False False False d a t a True False False False True e m o True s b False False True b a c? s? s? e? NO! csse is not found in the trie TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba

20. SEARCHING ALGORITHM C False s False e True True root False False False d a t a True False False False True e m o False True s b False False True b a public boolean search (String word) { return searchRecursive(root, word, 0); } private boolean searchRecursive( TrieNode current, String word, int index) { if (index == word.length ()) { . return current.endOfWord ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null) { return false; } return searchRecursive(node, word, index + 1); } Search: bba Index = 0 ch = b b ? Index = 1 ch = b b ? Index = 2 ch = a a? Index = 3 True? Return True Otherwise return false

21. TIME COMPLEXITY Average Length of word = l Time Complexity Of Searching : O( l )

22. DELETION

23. C False s False e True True root False False False d a t a True False False False True e m o True s b False False True b a TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba Remove: cs C? s? TRUE? False cs Deleted!

24. C False s False e True True root False False False d a t a True False False False True e m o True s b False False True b a TrieNode { Map< Character , TrieNode > children; boolean endOfWord ; } cs cse data demo css bba Remove: bba b ? b ? a? remove bba Deleted! remove

25. root Remove: cs C False s False e True True False False False d a t a True True s b a public void delete(String word) { delete(root, word, 0); } private boolean delete( TrieNode current, String word, int index) { if (index == word.length ()) { if (! current.endOfWord ) { return false;} current.endOfWord = false; return current.children.size () == 0 ; } char ch = word.charAt (index); TrieNode node = current.children.get ( ch ); if (node == null) { return false;} boolean shouldDeleteCurrentNode = delete(node, word, index + 1); if ( shouldDeleteCurrentNode ) { current.children.remove ( ch ); return current.children.size () == 0;} return false ;} d elete(“ cs ”) delete(root,“cs”,0) Ch = c C? node delete(s,“cs”,1) Ch = s s? node delete(e,“cs”,2) False False False False False CS Removed