Data Structure, Trie & JAVA구현

TrieNode.java

package org.dataStructure;

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

// 자식노드맵 + 현재 노드가 마지막 글자인지 여부 (한 단어가 완성되는 시점임을 알 수 있다)
public class TrieNode {

	// 자식 노드 맵
	private Map<Character, TrieNode> childNodes = new HashMap<>();

	// 마지막 글자인지 여부
	private boolean isLastChar;


	Map<Character, TrieNode> getChildNodes(){
		return this.childNodes;
	}

	boolean isLastChar() {
		return this.isLastChar;
	}

	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
}

Trie.java

package org.dataStructure;

// Trie는 기본적으로 빈 문자열을 가지는 루트노드만 가지고 있다.
// insert메서드를 통해 단어를 입력하면서 그에 맞게 자식 노드가 생성된다.
public class Trie {

	// 루트 노드
	private TrieNode rootNode;

	Trie() {
		rootNode = new TrieNode();
	}

	// 자식 노드 추가
	void insert(String word) {
		TrieNode thisNode = this.rootNode;

		for (int i = 0; i < word.length(); ++i) {
			thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
		}

		// 계속해서 thisNode를 갱신하기 때문에 마지막 글자가 되므로 true.
		thisNode.setIsLastChar(true);
	}

	// 특정 단어가 Trie에 존재하는지 확인
	// 1. 루트노드 부터 순서대로 알파벡이 일치하는 자식노드들이 존재 할것
	// 2. 해당 단어의 마지막 글자에 해당하는 노드의 isLastChar == true 일것
	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();
	}

	// 삭제
	// 탐색 : 부모노드 -> 자식노드
	// 삭제 : 자식노드 -> 부모노드
	// 1. 자식 노드를 가지고 있지 않아야 합니다.
	// 삭제시, 자식노드까지 지우면 안된다.
	// 2. 삭제 시작 첫 노드는 isLastChar == true여야한다.
	// false이면 존재하지 않는 단어이기 때문에 삭제 불가능.
	// 3. 삭제 진행 중에는 isLastChar == false 여야한다.
	// true이면 다른 단어가 존재하기 때문에 삭제하면 안된다.

	void delete(String word) {
		delete(this.rootNode, word, 0); // 최초로 delete 시작.
	}

	private void delete(TrieNode thisNode, String word, int index) {

		char character = word.charAt(index);

		// 단어가 아예존재 하지 않는경우 , ex) ABC , DEF
		if (!thisNode.getChildNodes().containsKey(character))
			throw new Error("There is no [" + word + "] in this Trie.");

		// 글자가 존재하는 trieNode를 가져온다
		TrieNode childNode = thisNode.getChildNodes().get(character);
		index++;

		// 탐색완료
		if (index == word.length()) {
			// 삭제 조건 2번 항목
			if (!childNode.isLastChar())
				throw new Error("There is no [" + word + "] in this Trie.");

			childNode.setIsLastChar(false);

			// 삭제 조건 1번 항목
			if (childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(childNode);

		} else {
			// 콜백함수
			delete(childNode, word, index);

			// 콜백함수로 인해서 단어 탐색이 완료된 후에 이부분이 불린다.
			// 삭제 조건 1, 3번 항목
			// 자식노드가 없고, 현재 노드로 끝나는 단어가 없는 경우 이 노드 삭제
			if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(character);
		}
	}

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

}

TrieTest.java

package org.dataStructure;

public class TrieTest {

	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.insert("DEV");
		trie.insert("DEAR");
		trie.insert("DESERVE");
		trie.insert("DRIVE");

		System.out.println(trie.contains("DEAR"));
		System.out.println(trie.contains("DESERT"));

		//trie.delete("DESERT");
		//trie.delete("DE");

		trie.delete("DEAR");
		System.out.println(trie.contains("DEAR"));

	}

}

---

참고

• https://the-dev.tistory.com/2