Trie

Posted on | In | Comments: | Views:

what

Trie, is actually a more general tree, also prefix tree.

Used for massive words process, dictionary representation, and lexicographic sorting, word frequency calc.

How

I. TrieNode

TrieNode has mainly two parts:

  1. children, to link next possible characters appear in a words. If only considering ‘A-Z’, there is 26 children at most
  2. info used to record current TrieNode
    • isWord, denotes previous character is a word or not.
    • cnt, denotes number of words consist of current prefix

Note: this representation is a little different from binary tree, in which info data are stored for current Node. However, in Trie, info data are stored for previous Node, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
For dictionary: { "a", "bd", "c" }, the Trie would be represented as following:

root TrieNode(0xefe4)
- cnt: 0
- isWord: false
- children:{'a': TrieNode , 'b': TrieNode, 'c': TrieNode, ... }
            /				      |				          \
            TrieNode(0xffe3)	TrieNode(0xffe4)   			TrieNode(0xffe5)
            - cnt: 1			- cnt: 0					- cnt: 1
            - isWord: true		- isWord: false				- isWord: false
            - children: null	- children: {'d':TrieNode}  - children: null
                                    |
                                   ...

Implementation

  • interfaces

    • build (constructor)
    • isWord
    • countWord
    • insert
    • delete
    • hasPrefix
    • getPrefixNode

  • Time Complexity: [ n words, K is number of characters of the longest word ]

    • build: O(nK)
    • isWord: O(K)
    • countWord: O(K)
    • insert: O(K)
    • delete: O(K)

  • Space Complexity: [N is the number of all characters appears in the dictionary ]

    • too much space: O(N) +O(N^2) +O(N^3) +O(N^4) + O(N^K)
    • good news is: when it is a really dictionary, all the space will be filled up, so not so much waste

  • delete might be a little complex. The to-be-deleted word possibly :

    1
    2
    3
    4
    5
    6
    when need delete a node, what should really to be done????
        - delete the key from HashMap<Character, Node>
        - reset to null when using Node[]
    So, always ask two questions:
    	- the node to be deleted, is part of other long word [by checking 'children']?
        - the node itself is the end of a word? [by checking 'isWord' & 'cnt']?
    • null, empty string, not exists in the Trie
    • contains other short words: “abc”, “ab”
      • recursively from bottom to top delete node, till the longest prefix
    • has same words as itself: “abc”, “abc”
      • don’t delete node, only update cnt
    • being a prefix of other long words: “abc”, “abcde”
      • don’t delete node, only update isWord
    • share prefix with other words: “abc”, “abd”
      • recursively from bottom to top delete node, till the longest prefix
    • only itself in the dictionary, not affect others “abc”
      • delte all nodes
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

import java.util.*;

class Node {
	public int cnt;
	public boolean isWord;
	public Map<Character, Node> children;

	public Node(){
		this.cnt = 0;
		this.isWord = false;
		this.children = new HashMap<>();
	}
}


class Trie{
	Node root;
	public Trie( String[] strArr ){
		this.root = new Node();
		for( String str : strArr ){
			insert( str );
		}
	}

	public boolean hasPrefix(String str ){
		if( str == null || str.length() == 0 ) return true;
		int len = str.length();
		Node cur = this.root;
		for( int i = 0; i < len; i++ ){
			char ch = str.charAt(i);
			if( !cur.children.containsKey(ch) ) return false;
			cur = cur.children.get(ch);
		}
		return true;
	}

	public Node getPrefixNode (String str){
		if( !hasPrefix(str) ) return null;
		int len = str.length();
		Node cur = this.root;
		for( int i = 0; i < len; i++ ){
			char ch = str.charAt(i);
			cur = cur.children.get(ch);
		}
		return cur;
	}

	public void insert( String str ){
		if( str == null || str.length() == 0 ) return;
		int len = str.length();
		Node cur = this.root;
		for( int i = 0; i < len; i++ ){
			char ch = str.charAt(i);
			if( !cur.children.containsKey(ch) ){
				cur.children.put( ch, new Node() );
			}
			cur = cur.children.get(ch);
		}
		cur.cnt++;
		cur.isWord = true;
	}

	public void delete (String str ){
		if( str == null || str.length() == 0 ) return;
		if( !hasPrefix(str) ) return;
		Node cur = getPrefixNode(str);
		cur.cnt--; 
		if(cur.cnt < 0) cur.cnt = 0;
		if(cur.cnt > 0) return; 	// at this position, there still word exist
		else{						// at this position, there no word exist
			if( cur.children.size() > 0 ) {	// but can be prefix of other words
				cur.isWord = false;
				return;
			}else{							// not a word, nor a prefix of others
				deleteNode(str);
			}
		}
		
	}
	public void deleteNode( String str ){
		int len = str.length();
		if( len == 0 ) return;

		String prevStr = str.substring(0, len-1);
		Node prevNode = getPrefixNode(prevStr);
		prevNode.children.remove(str.charAt(len-1));
		if( prevNode.children.size()==0 && prevNode.cnt==0 ) delete(prevStr);
		return;
	}
	

	public boolean isWord( String str ){
		if( !hasPrefix(str) ) return false;
		return getPrefixNode(str).isWord;
	}	

	public int countWord( String str ){
		if( !hasPrefix(str) ) return 0;
		return getPrefixNode(str).cnt;
	}

	
}

class TrieTree{
	public static void main( String[] args ){
		String[] dict = { "a", "ab", "ab", "abc", "abc", "abc", "abcd", "ac", "acd", "ad", "2,24",  "2,2,4" };
		Trie trieTree = new Trie(dict);
		
		// String isWordTest1 = "ab";
		// String isWordTest2 = "";
		// String isWordTest3 = "a";
		// String isWordTest4 = "abcd";
		// String isWordTest5 = "abcde";

		// String countTest = "abc";
		// String insertTest = "abc";
		

		// System.out.println( trieTree.isWord(isWordTest1));
		// System.out.println( trieTree.isWord(isWordTest2));
		// System.out.println( trieTree.isWord(isWordTest3));
		// System.out.println( trieTree.isWord(isWordTest4));
		// System.out.println( trieTree.isWord(isWordTest5));


		// System.out.println( trieTree.countWord(countTest));
		// trieTree.insert(insertTest);
		// System.out.println( trieTree.countWord(countTest));
		// trieTree.insert(insertTest);
		// System.out.println( trieTree.countWord(countTest));


		// String hasPrefixTest1 = "abcd";
		// String hasPrefixTest2 = "2,2";
		// String hasPrefixTest3 = "abcdd";
		// System.out.println( trieTree.hasPrefix(hasPrefixTest1));
		// System.out.println( trieTree.hasPrefix(hasPrefixTest2));
		// System.out.println( trieTree.hasPrefix(hasPrefixTest3));


		String deleteTest1 = "abcd";
		String deleteTest2 = "abc";
		String deleteTest3 = "ab";
		trieTree.delete(deleteTest1);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 3
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();

		trieTree.delete(deleteTest1);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 3
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();

		trieTree.delete(deleteTest2);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 2
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		trieTree.delete(deleteTest2);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 1
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		
		trieTree.delete(deleteTest2);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 0
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		

		trieTree.delete(deleteTest2);
		System.out.println( trieTree.countWord(deleteTest3)); // 2
		System.out.println( trieTree.countWord(deleteTest2)); // 0
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		

		trieTree.delete(deleteTest3);
		System.out.println( trieTree.countWord(deleteTest3)); // 1
		System.out.println( trieTree.countWord(deleteTest2)); // 0
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		

		trieTree.delete(deleteTest3);
		System.out.println( trieTree.countWord(deleteTest3)); // 0
		System.out.println( trieTree.countWord(deleteTest2)); // 0
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
		

		trieTree.delete(deleteTest1);
		System.out.println( trieTree.countWord(deleteTest3)); // 0
		System.out.println( trieTree.countWord(deleteTest2)); // 0
		System.out.println( trieTree.countWord(deleteTest1)); // 0
		System.out.println();
		
	}
}