A trie (or a prefix tree) is a data structure similar to n-ary trees, where each node can have n children. Each child holds a reference to the next n children.
Here an example trie is discussed where some words are stored in the trie.
The TrieNode consists of the following elements:
class TrieNode {
boolean isWord = false;
TrieNode[] children = new TrieNode[26];
}
Here each node can have 26 children. Some children may point to null and others may point to the next character in the word.
For example, when the words "home" and "hot" are added to the trie, the state of the trie can be described as follows:
1. The first level will hold 26 children with only the 8th ("h") child holding a non-null reference. Rest of the 25 children will be null.
2. The second level which is the children of "h" will hold 25 null children with only the 15th ("o") child holding a non-null reference.
3. The third level will which is the children of "o" will hold 2 non-null references ("m" and "t") and rest 24 children will be null.
4. The fourth level will have one non-null reference ("e"), which is one of the children of "m", and "t" will hold 26 null references.
Java Code:
Unit Tests:
Trie printed in level order:
Here an example trie is discussed where some words are stored in the trie.
The TrieNode consists of the following elements:
class TrieNode {
boolean isWord = false;
TrieNode[] children = new TrieNode[26];
}
Here each node can have 26 children. Some children may point to null and others may point to the next character in the word.
For example, when the words "home" and "hot" are added to the trie, the state of the trie can be described as follows:
1. The first level will hold 26 children with only the 8th ("h") child holding a non-null reference. Rest of the 25 children will be null.
2. The second level which is the children of "h" will hold 25 null children with only the 15th ("o") child holding a non-null reference.
3. The third level will which is the children of "o" will hold 2 non-null references ("m" and "t") and rest 24 children will be null.
4. The fourth level will have one non-null reference ("e"), which is one of the children of "m", and "t" will hold 26 null references.
Java Code:
package com.sourabh.third;
import java.util.LinkedList;
import java.util.Queue;
class TrieNode {
boolean isWord = false;
TrieNode[] children = new TrieNode[26];
public TrieNode() {
}
public TrieNode(String key) {
this.add(key);
}
public boolean contains(String in) {
TrieNode node = this;
for(int i=0; i<in.length();i++) {
TrieNode child = node.children[getAscii(in.charAt(i))];
if(child == null) {
// This particular character is not present in the current branch.
return false;
}
else {
if(in.length() - 1 == i) {
// We have reached the end of the input string.
return true;
}
else {
node = child;
}
}
}
return false;
}
public void add(String in) {
if(in.length() == 0) {
this.isWord = true;
return;
}
else {
char first = in.charAt(0);
TrieNode child = children[getAscii(first)];
if(child == null) {
child = new TrieNode();
children[getAscii(first)] = child;
}
child.add(in.substring(1));
}
}
public int getAscii(char c) {
char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int i=0;
for(i=0;i<A.length;i++) {
if(A[i] == c) {
break;
}
}
return i;
}
}
public class TriePrograms {
public TrieNode createNode(String word) {
if(word == null) {
return new TrieNode();
}
else {
return new TrieNode(word);
}
}
public void levelOrderTraversal(TrieNode node) {
Queue<TrieNode[]> queue = new LinkedList<>();
if(node == null) {
return;
}
queue.add(node.children);
int thisLevel = 1;
int nextLevel = 0;
while(!queue.isEmpty()) {
for(int ele = 0; ele < thisLevel; ele++) {
TrieNode[] childrenAtThisLevel = queue.remove();
for(int i=0; i<childrenAtThisLevel.length; i++) {
if(childrenAtThisLevel[i] != null) {
System.out.print(getChar(i) + ".");
queue.add(childrenAtThisLevel[i].children);
nextLevel++;
}
else {
System.out.print(".");
}
}
}
thisLevel = nextLevel;
System.out.println();
for(int i=0;i<26;i++) {
System.out.print("-");
}
System.out.println();
for(int i=0;i<26;i++) {
System.out.print("|");
}
System.out.println();
nextLevel = 0;
}
thisLevel = nextLevel;
}
public char getChar(int ascii) {
char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
return A[ascii];
}
}
Unit Tests:
package com.sourabh.third;
import org.junit.Assert;
import org.junit.Test;
public class TrieProgramTests {
TriePrograms instance = new TriePrograms();
@Test
public void testContains() {
TrieNode node = instance.createNode(null);
node.add("home");
Assert.assertTrue(node.contains("home"));
node.add("house");
Assert.assertTrue(node.contains("house"));
node.add("hot");
Assert.assertTrue(node.contains("hot"));
Assert.assertFalse(node.contains("hole"));
}
@Test
public void testConstructor() {
TrieNode node = instance.createNode("home");
Assert.assertTrue(node.contains("home"));
node.add("house");
Assert.assertTrue(node.contains("house"));
node.add("hot");
Assert.assertTrue(node.contains("hot"));
Assert.assertFalse(node.contains("hole"));
}
@Test
public void testLevelOrderTraversal() {
TrieNode node = instance.createNode("home");
node.add("house");
node.add("hot");
instance.levelOrderTraversal(node);
}
}
Trie printed in level order:
.......h................... -------------------------- |||||||||||||||||||||||||| ..............o............ -------------------------- |||||||||||||||||||||||||| ............m.......t.u...... -------------------------- |||||||||||||||||||||||||| ....e..................................................................s........ -------------------------- |||||||||||||||||||||||||| ..............................e...................... -------------------------- |||||||||||||||||||||||||| .......................... -------------------------- ||||||||||||||||||||||||||
