[DataStructure] Trie-2 : Implementation Trie using Java

 

Hello, this is Dev_dog.

 

In this post, I'm gonna explain how to implement Trie data structure using Java8.
If you find any errors or have any questions, feel free.

 

You can check the former post via the link below : 
[EN/DATA STRUCTURE] - [DataStructure] Trie-1 : The Basis of The Trie Data Structure

 

 

 한글 포스트는 아래 링크에서 보실 수 있습니다 : 
[KR/자료구조] - [자료구조] Trie(트라이)-2 : 자바로 구현하기

 

 

 

 

---

 

 

Implementation Trie using Java

 

Creating Classes

 To implement Trie using Java, we need to create both Trie and TrieNode Classes.
 Let's begin with the class TrieNode.

 

TrieNode.java

 TrieNode has child node maps and whether the current node is the last character.
 In the word 'POW', for exmaple,  [P], and [O] are not the last characters, but [W] is.
 To notify the point where the whole word is completed, we will set the boolean at the last character.

public class TrieNode {
	
}

Creating TrieNode class

public class TrieNode {

	// [ Variables ]
	// Child node map
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// Whether it is the last character
	private boolean isLastChar;
	
}

Adding variables to the TrieNode class

 

 

 Once these two variables are assigned, you need getters and a setter to access them.
 Since the child nodes will be created and placed in the Trie class,
only the getter will be created for the variable childNodes.

 The last character variable can be changed in the process of deleting the node,
so both a getter and setter need to be created.

public class TrieNode {

	// [ Variable ]
	// Child node map
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// Whether it is the last character
	private boolean isLastChar;
	
	// [ GETTER / SETTER method ]
	// Getter for the childNodes map
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	// Getter for the variable isLastChar
	boolean isLastChar() {
		return this.isLastChar;
	}
	// Setter for the variable isLastChar
	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
	
}

Adding Methods to the TrieNode class

 

Trie.java

 By default, Trie only has a root node with an empty string.
 By inserting a word through the 'insert' method, a child node is created accordingly.

public class Trie {

}

Creating Trie class

public class Trie {

	// [ Variable ]
	// Root node
	private TrieNode rootNode;

}

Adding a Varible to the Trie class

 

 

 First, when the trie is created, the rootNode is created through the constructor.

public class Trie {

	// [ Variable ]
	// Root node
	private TrieNode rootNode;

	// [ Constructor ]
	Trie() {
		rootNode = new TrieNode();
	}
    
}

Adding a Constructor to the Trie class

 

 

---

 

Method Implementation

 Now, let's create three methods to insert a word into the Trie data structure, make sure that the Trie contains the word, and delete a certain word from Trie.

 

1. insert

 Put each alphabet of input word into child nodes of hierarchical structure.
 At this time, if the same alphabet already exists in the corresponding position,
common prefix part will not be generated.
 That means, it creates child nodes only when the child does not exist in the position where they need to be (using lambda: this is the reason why we use Java8).

 For example, when you try to insert 'DEAR' in the Trie that already contains 'DEV',
'DE-' is a duplicate, so only '-A-R' under 'DE-' need to be inserted.

 In the last character, setIsLastChar(true) indicates that there is a word completed here.

// Inserting child nodes
void insert(String word) {
	TrieNode thisNode = this.rootNode;

	for (int i = 0; i < word.length(); i++) {
    	// Create child nodes only when they don't exist where they has to be
		thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
	}
	thisNode.setIsLastChar(true);
}

Insert method of the Trie class

 

2. contains

 The following two conditions must be met in order to verify that the Trie contains a certain word.

• Child nodes with alphabetical order from root node must exist.
• The variable isLastChar of the last character's node should be true.
  (Meaning that there is a word that completed by the character)

 At this point, we must keep in mind the second condition.
 For example, if there is a Trie that only has the words 'POW' and 'PIE',
and assuming that we are going to searche for the word 'PI'.
 'PI' matches the part 'PI-' of 'PIE'', so it matches condition 1 (PI is included in the PIE).

 However, since 'insert' method only setsIsLastChar(true) for '-E' of 'PIE', You will be able to verify that the word is not in Trie because it does not match condition 2.

// Checking the Trie contains a specific word
boolean contains(String word) {
	TrieNode thisNode = this.rootNode;

	for (int i = 0; i < word.length(); i++) {
		char character = word.charAt(i);
		TrieNode node = thisNode.getChildNodes().get(character);

		if (node == null)
			return false;

		thisNode = node;
	}

	return thisNode.isLastChar();
}

Contains Method of the Trie class

 

3. delete

 Finally, it is about the process of deleting a certain word from the Trie.
 To find a target word, going down to the corresponding child nodes by the word length.

 Note that since the nodes do not have the information of the parent node,
it is necessary to go down to the child node to search for the word to be deleted,
and delete it in the way going backwards (callback).

• Search Process Direction : Parent Node → Child Node
• Delete Process Direction : Child NOde → Parent Node

 

Figure1. An Example of the Trie

 

Let's look at the following conditions to delete a certain word.

1. It should not have child nodes.
   If you delete 'PI' in the above figure, 'PIE' will be deleted as well.
2. The first node to delete must be 'isLastChar == true'.
   If it is false, it means a word not in the Trie.
   For example, the word "PO" in the picture above is a word that Trie does not have,
   even if it can be seen by our own eyes.
3. While deleting nodes(which means not the first deleting node), those have to be 'isLastChar == false'.
   Since isLastChar is true in the deleting process, it means that there is another word.
   Assuming that we try to delete a word 'PIE' from the picture above, '-E' will be deleted first.
   Then 'I' is the next target node but it's 'isLastChar' is true which means there is another word 'PI'.
   And we are not going to delete no more.

In the source code, in addition,  a new Error will be thrown when the delete-target-word does not exist.

// Deleting a certain word
void delete(String word) {
    delete(this.rootNode, word, 0);
}
	
private void delete(TrieNode thisNode, String word, int index) {
		
    char character = word.charAt(index);
    
    if(!thisNode.getChildNodes().containsKey(character))
    	throw new Error("There is no [" + word + "] in this Trie.");
        
	TrieNode childNode = thisNode.getChildNodes().get(character);
	index++;
    
	if(index == word.length()) {
		if (!childNode.isLastChar()) throw new Error("There is no [" + word + "] in this Trie.");
			
		childNode.setIsLastChar(false);
	
	if (childNode.getChildNodes().isEmpty())
		thisNode.getChildNodes().remove(character);
	}else {
		delete(childNode, word, index); // callback part
		if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty()) 
			thisNode.getChildNodes().remove(character);
	}
}

Delete Method of the Trie class

 

Additional Methods for tests

boolean isRootEmpty() {
	return this.rootNode.getChildNodes().isEmpty();
}

 

---

 

Final Sources

TrieNode.java

import java.util.HashMap;
import java.util.Map;

public class TrieNode {

	// [ Variable ]
	// Child node map
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// Whether it is the last character
	private boolean isLastChar;
	
	// [ GETTER / SETTER method ]
	// Getter for the childNodes map
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	// Getter for the variable isLastChar
	boolean isLastChar() {
		return this.isLastChar;
	}
	// Setter for the variable isLastChar
	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
	
}

 

Trie.java

public class Trie {

	// [ Variable ]
	// Root node
	private TrieNode rootNode;

	// [ Constructor ]
	Trie() {
		rootNode = new TrieNode();
	}

	// [ Methods ]
	// Inserting child nodes
	void insert(String word) {
		TrieNode thisNode = this.rootNode;

		for (int i = 0; i < word.length(); i++) {
	    	// Create child nodes only when they don't exist where they has to be
			thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
		}
		thisNode.setIsLastChar(true);
	}
    
	// Checking the Trie contains a specific word
	boolean contains(String word) {
		TrieNode thisNode = this.rootNode;

		for (int i = 0; i < word.length(); i++) {
			char character = word.charAt(i);
			TrieNode node = thisNode.getChildNodes().get(character);

			if (node == null)
				return false;

			thisNode = node;
		}

		return thisNode.isLastChar();
	}
    
	// Deleting a certain word
	void delete(String word) {
		delete(this.rootNode, word, 0);
	}
	
	private void delete(TrieNode thisNode, String word, int index) {
		
		char character = word.charAt(index);
    
		if(!thisNode.getChildNodes().containsKey(character))
			throw new Error("There is no [" + word + "] in this Trie.");
        
		TrieNode childNode = thisNode.getChildNodes().get(character);
		index++;
    
		if(index == word.length()) {
			if (!childNode.isLastChar()) throw new Error("There is no [" + word + "] in this Trie.");
			
			childNode.setIsLastChar(false);
	
			if (childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(character);
		}else {
			delete(childNode, word, index); // callback part
			if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty()) 
				thisNode.getChildNodes().remove(character);
		}
	}
    
}

 

---

 

---

 

Tests using Junit

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class TestTrie {

	@Test
	public void trieTest() {
		Trie trie = new Trie();
		
		// tests for an Insert method
		assertTrue(trie.isRootEmpty());
		
	    trie.insert("PI");
	    trie.insert("PIE");
	    trie.insert("POW");
	    trie.insert("POP");
	    
	    assertFalse(trie.isRootEmpty());
	    
	    // tests for a Contains method
	    assertTrue(trie.contains("POW"));
	    assertFalse(trie.contains("PIES"));
	    
	    // tests for a Delete method
	    trie.delete("POP");
	    assertFalse(trie.contains("POP"));
	    assertTrue(trie.contains("POW"));
	    
	    // throwing an error caused by trying to delete not-exists-word
	    trie.delete("PIES");
	}
}

Only attempts to delete words that are not in the Trie will throw an error.

 

 

---

 

 

This post was written with the following reference.

 

https://www.baeldung.com/trie-java

Trie Data Structure in Java | Baeldung