Algorithm/Trie datastructure at master · TechRaY/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

import java.io.*;
import java.util.*;

public class Trie {

    private class TrieNode
    {
        HashMap<Character,TrieNode> children;
        boolean endofword;

        public TrieNode()
        {
            children=new HashMap();
            endofword=false;
        }
    }

    private final TrieNode root;

    public Trie()
    {
        root=new TrieNode();
    }


    public void insert(String word)                 //Iterative Insert
    {
        TrieNode current=root;
        int len=word.length();

        for(int i=0;i<len;i++)
        {
            char ch=word.charAt(i);

            TrieNode node =current.children.get(ch);

            if(node==null)
            {
                node=new TrieNode();
                current.children.put(ch,node);
            }

            current=node;
        }

        current.endofword=true;
    }


     public boolean search(String word)                      //Search for the word
     {
        TrieNode current=root;
        int len=word.length();
        for(int i=0;i<len;i++)
        {
            char ch=word.charAt(i);
            TrieNode node=current.children.get(ch);

            if(node==null)
            return false;

            current=node;
        }

        return current.endofword;
     }


     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;
     }


    public static void main(String args[])
    {
        Trie triechecker=new Trie();

        triechecker.insert("rajeev");

        if(triechecker.search("rajeev"))
        System.out.println(" exists");

        if(!triechecker.search("raneev"))
        System.out.println("not exists");

    }
}