[자료구조] Trie(트라이)-2 : 자바로 구현하기

티스토리 뷰

KR/자료구조

[자료구조] Trie(트라이)-2 : 자바로 구현하기

개발개 2019. 7. 21. 01:07

728x90

안녕하세요. 개발개입니다.

지난 시간 기초 개념에 이어, Trie를 자바로 구현하는 과정을 알아보겠습니다.
구현 과정에서 람다를 사용하기 때문에 Java8이상으로 진행합니다.

[KR/자료구조] - [자료구조] Trie(트라이)-1 : 기초 개념

오타, 오류 혹은 기타 의견은 언제든지 환영합니다.

자바(Java)에서 Trie 구현하기

클래스 생성

자바로 Trie 자료구조를 구현하기 위해서는 자료구조인 Trie와 이를 구성할 TrieNode 클래스가 각각 필요합니다.
먼저 TrieNode 클래스부터 보겠습니다.

TrieNode.java

TrieNode는 자식노드맵과 현재 노드가 마지막 글자인지 여부에 대한 정보를 가지고 있습니다.
여기에서 마지막 글자 여부란 'DEV'라는 단어에서 [D], [E]는 마지막 글자가 아니지만 [V]는 마지막 글자로, 한 단어가 완성되는 시점임을 알 수 있도록 하는 불린 값입니다.

public class TrieNode {
	
}

TrieNode 클래스 생성

public class TrieNode {

	// [ 변수 ]
	// 자식 노드 맵
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// 마지막 글자인지 여부
	private boolean isLastChar;
	
}

TrieNode 클래스에 변수 추가

이렇게 두 변수가 할당되었으면 이 변수에 접근할 수 있는 Getter와 Setter가 필요합니다.
자식노드는 Trie 차원에서 생성해서 넣을 것이기 때문에 Getter만 생성해 줍니다.
마지막 글자 여부는 추후 노드 삭제하는 과정에서 변경이 필요하기 때문에 Getter와 Setter를 둘 다 생성해 줍니다.

public class TrieNode {

	// [ 변수 ]
	// 자식 노드 맵
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// 마지막 글자인지 여부
	private boolean isLastChar;
	
	// [ GETTER / SETTER 메서드 ]
	// 자식 노드 맵 Getter
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	// 마지막 글자인지 여부 Getter
	boolean isLastChar() {
		return this.isLastChar;
	}
	// 마지막 글자인지 여부 Setter
	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
	
}

TrieNode 클래스에 메서드 추가

Trie.java

Trie는 기본적으로 빈 문자열을 가지는 루트노드만 가지고 있습니다.
이 후에 나올 insert 메서드를 통해 단어를 넣음으로써 그에 맞게 자식 노드가 생성됩니다.

public class Trie {

}

Trie 클래스 생성

public class Trie {

	// [ 변수 ]
	// 루트 노드
	private TrieNode rootNode;

}

Trie 클래스 변수 추가

우선 Trie가 생성되면 rootNode가 생성될 수 있도록 생성자를 통해 rootNode를 생성해 줍니다.

public class Trie {

	// [ 변수 ]
	// 루트 노드
	private TrieNode rootNode;

	// [ 생성자 ]
	Trie() {
		rootNode = new TrieNode();
	}
    
}

Trie 클래스 생성자 추가

메서드 구현

이제 본격적으로 Trie 자료구조에 단어 정보를 저장(insert)하고, 해당 단어가 존재하는지 확인(contains)하고, Trie에서 특정 단어를 삭제(delete)하는 세 가지 메서드를 만들어보겠습니다.

1. insert

입력받은 단어의 각 알파벳을 계층구조의 자식노드로 만들어 넣습니다.
이 때, 이미 같은 알파벳이 존재하면 공통 접두어 부분까지는 생성하지 않습니다.
즉, 해당 계층 문자의 자식노드가 존재하지 않을 때에만 자식 노드를 생성해줍니다(여기서 람다식을 사용).

예를 들면, 이미 'DEV'가 들어있는 Trie에 'DEAR'를 넣을 때, 'DE-'는 중복이므로 'D-E-'노드 아래 '-A-R'만 추가로 자식노드를 생성해 주는 것입니다.

그리고 마지막 글자에서는 여기까지를 끝으로 하는 단어가 존재한다는 표시를 위해 setIsLastChar(true) 해줍니다.

// 자식 노드 추가
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.setIsLastChar(true);
}

Trie 클래스의 insert 메서드

2. contains

특정 단어가 Trie에 존재하는지를 확인하기 위해서는 다음 두 가지 조건을 만족시켜야 합니다.

루트노드부터 순서대로 알파벳이 일치하는 자식노드들이 존재 할 것
해당 단어의 마지막 글자에 해당하는 노드의 isLastChar가 true일 것
(해당 글자를 마지막으로 하는 단어가 있다는 뜻)

여기서 두 번째 조건에 유념해야 합니다.
예를 들어, Trie에는 'POW'와 'PIE'라는 단어만 등록되어 있는데, 'PI'라는 단어를 검색한다고 가정합니다.
'PI'는 'PIE'와 'PI-'가 일치하기 때문에 1번 조건에는 부합(PI가 PIE에 포함되는 단어)하지만, insert 메서드에서 'PIE'의 '-E'에만 setIsLastChar(true) 했기 때문에 2번 조건에는 부합하지 않아 Trie에 없는 단어임을 확인 할 수 있게 됩니다.

// 특정 단어가 들어있는지 확인
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();
}

Trie 클래스의 contains 메서드

3. delete

마지막으로 Trie에 넣었던 단어를 삭제하는 과정입니다.
contains 메서드처럼 주어진 단어를 찾아 하위 노드로 단어 길이만큼 내려갑니다.
주의할 점은 노드들이 부모노드의 정보를 가지고 있지 않기 때문에, 하위 노드로 내려가며 삭제 대상 단어를 탐색하고 다시 올라오며 삭제하는 과정이 콜백(callback) 형식으로 구현되어야 한다는 점입니다.

탐색 진행방향 : 부모 노드 → 자식 노드
삭제 진행방향 : 자식 노드 → 부모 노드

삭제 진행은 마지막 글자에서 부모 노드 방향으로 되돌아 오는 과정에서 진행된다는 점에 유의하여 다음 삭제 조건들을 살펴봅니다.

자식 노드를 가지고 있지 않아야 합니다.
위 그림에서 'PI'를 지워버리면 'PIE'까지 삭제되어 버리기 때문입니다.
삭제를 시작하는 첫 노드는 isLastChar==true여야 합니다.
false인 경우는 Trie에 없는 단어란 뜻이기 때문입니다.
예를 들어, 위 그림에서 'PO'이라는 글자를 지우라고 명령을 내려도 Trie가 가지고 있지 않는 단어라는 점입니다.
삭제를 진행하던 중에는 isLastChar==false여야 합니다.
삭제 과정 중에서 isLastChar가 true라는 것은 또다른 단어가 있다는 의미이므로 삭제 대상이 아닙니다.
'PIE'를 삭제 대상으로 했을 때, '-E'를 삭제후 'PI'라는 단어의 'I'가 isLastChar==true이므로 또다른 단어가 있음을 알려줍니다.

참고로, 삭제 대상 단어의 마지막 글자가 isLastChar false이거나 해당하는 마지막 글자가 없는 경우는 new Error를 던지도록 구현했습니다.

// 특정 단어 지우기
void delete(String word) {
	delete(this.rootNode, word, 0); // 최초로 delete 던지는 부분
}
	
private void delete(TrieNode thisNode, String word, int index) {
		
	char character = word.charAt(index);
  
	// APPLE, PEN과 같이 아예 없는 단어인 경우 에러 출력
	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()) {
		// 삭제조건 2번 항목
		// PO와 같이 노드는 존재하지만 insert한 단어가 아닌 경우 에러 출력
		if (!childNode.isLastChar()) throw new Error("There is no [" + word + "] in this Trie.");
			
		childNode.setIsLastChar(false);
		// 삭제조건 1번 항목
		// 삭제 대상 언어의 제일 끝으로써 자식 노드가 없으면(이 단어를 포함하는 더 긴 단어가 없으면) 삭제 시작
		if (childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(character);
	}else {
		delete(childNode, word, index); // 콜백함수부분
		// 삭제조건 1,3번 항목
		// 삭제 중, 자식 노드가 없고 현재 노드로 끝나는 다른 단어가 없는 경우 이 노드 삭제
		if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(character);
	}
}

Trie 클래스의 delete 메서드

테스트를 위해 추가한 부수적인 메서드

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

최종소스

TrieNode.java

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

public class TrieNode {

	// [ 변수 ]
	// 자식 노드 맵
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// 마지막 글자인지 여부
	private boolean isLastChar;
	
	// [ GETTER / SETTER 메서드 ]
	// 자식 노드 맵 Getter
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	// 마지막 글자인지 여부 Getter
	boolean isLastChar() {
		return this.isLastChar;
	}
	// 마지막 글자인지 여부 Setter
	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
	
}

Trie.java

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.setIsLastChar(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();
	}
    
	// 특정 단어 지우기
	void delete(String word) {
		delete(this.rootNode, word, 0); // 최초로 delete 던지는 부분
	}
	
	private void delete(TrieNode thisNode, String word, int index) {
		
		char character = word.charAt(index);

		// APPLE, PEN과 같이 아예 없는 단어인 경우 에러 출력
		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()) {
			// 삭제조건 2번 항목
			// PO와 같이 노드는 존재하지만 insert한 단어가 아닌 경우 에러 출력
			if (!childNode.isLastChar()) 
            	throw new Error("There is no [" + word + "] in this Trie.");

			childNode.setIsLastChar(false);
            
			// 삭제조건 1번 항목
			// 삭제 대상 언어의 제일 끝으로써 자식 노드가 없으면(이 단어를 포함하는 더 긴 단어가 없으면) 삭제 시작
			if (childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(character);
		}else {
			delete(childNode, word, index); // 콜백함수부분
			
			// 삭제조건 1,3번 항목
			// 삭제 중, 자식 노드가 없고 현재 노드로 끝나는 다른 단어가 없는 경우 이 노드 삭제
			if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(character);
		}
	}
}

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();
		
		// insert 메서드
		assertTrue(trie.isRootEmpty());
		
		trie.insert("PI");
		trie.insert("PIE");
		trie.insert("POW");
		trie.insert("POP");
	    
		assertFalse(trie.isRootEmpty());
	    
		// Contains 메서드
		assertTrue(trie.contains("POW"));
		assertFalse(trie.contains("PIES"));
	    
		// Delete 메서드
		trie.delete("POP");
		assertFalse(trie.contains("POP"));
		assertTrue(trie.contains("POW"));
	    
		// 없는 단어를 지울 때 > 에러발생하는 예
		trie.delete("PO");
		trie.delete("PIES");
		trie.delete("PEN");
	}
}

마지막 Trie에 없는 단어를 삭제 시도에서만 오류가 발생하게 됩니다.

본 글은 다음을 참고하여 작성되었습니다.

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

Trie Data Structure in Java | Baeldung

An introduction to the Trie data structure in Java.

www.baeldung.com

728x90

저작자표시 비영리 동일조건

'KR > 자료구조' 카테고리의 다른 글

[자료구조] Trie(트라이)-1 : 기초 개념 (0)	2019.07.20

Total

Today

Yesterday

« 2024/04 »
일	월	화	수	목	금	토
	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

04-24 05:16

DevLogs

티스토리 뷰