[Algorithm] Trie를 Java로 구현해보자!

---

안녕하세요 coding-knowjam입니다.

오늘은 검색할 때 O(N)의 시간 복잡도를 가지는 Trie를 구현해보겠습니다.

 

1. Trie란?

Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다.

정수형을 저장하는 Tree가 아래와 같은 모양으로 있다고 가정하겠습니다.

정수형 Tree

위와 같은 정수형 자료의 이진트리에서는 검색을 수행할 때 O(logN)의 시간 복잡도를 가지게 됩니다.

그러나 같은 이진트리 형태 이어도 문자열을 저장하고 있다면 문자열의 길이가 M일 때, O(M*logN)의 시간 복잡도를 가지게 됩니다.

이러한 문제를 해결하기 위해 Trie를 사용하게 됩니다.

 

Trie는 문자열 전체를 하나의 노드에 저장하는 게 아니라, 한 단어씩 노드에 저장하는 트리입니다.

Trie 자료구조

Trie는 루트 노드는 비어있고 첫 번째 자식 노드부터 문자열의 첫 단어가 저장됩니다.

현재 위 그림의 Trie에 저장된 문자는 cap, code, kakao, kai입니다.

Trie 자료구조는 문자열의 한 단어씩 자식 노드와 비교해가면서 검색을 진행할 수 있습니다.

예를 들어 cap을 검색한다면 c자식 노드 -> a자식 노드 -> p자식 노드 순으로 검색을 진행할 수 있습니다.

kakao를 검색한다면 k자식 노드 -> a자식 노드 -> k자식 노드 -> a자식 노드 -> o자식 노드

만약에 없는 단어를 검색한다면 어떻게 진행될까요??

coding을 검색한다면 c자식 노드 -> o자식 노드 -> d자식 노드 -> i값을 가지는 자식 노드는 없으므로 검색 불가

이러한 식으로 찾고자 하는 문자를 탐색하므로 문자열의 길이가 M일 때, 탐색 시간 복잡도는 O(M)을 가지게 되므로 매우 효율적이라고 할 수 있습니다.

 

2. Java코드로 구현

그렇다면 Trie 자료구조를 Java코드로는 어떻게 구현할 수 있을까요?

기본적으로는 Map Interface를 사용해서 구현하게 됩니다.

Map의 키 값에는 문자를 이루는 각각의 단어들이 들어가고, 키와 매핑되는 값에는 자식 노드 클래스가 저장됩니다.

글로만 보면 잘 이해가 안 되실 테니까 코드를 직접 보시기 전에 그림으로 먼저 살펴보겠습니다.

왼쪽은 Trie자료구조이고 오른쪽은 이를 Map을 통해서 구현할 때 key와 value로 매핑하는 코드를 그림으로 표현한 것입니다.

코드 구현 설명

전체적인 코드 구현은 위의 그림과 같이 진행되며 문자가 현재 Trie내부에 존재하는지 체크하기 위한 boolean 변수도 추가적으로 사용해야 합니다.

왜냐하면 예를 들어 bus와 busy를 구분하기 위해서는 s노드가 단어의 끝인지 아닌지를 체크하는 변수가 있어야 bus가 현재 Trie에 존재한다는 것을 알 수 있기 때문입니다.

 

그럼 실제 코드로 한번 구현해보겠습니다.

우선 가장 먼저 Node를 만들어야겠죠?

static class Node {
		// 자식노드
		Map<Character, Node> chiledNode = new HashMap<Character, Node>();
		// 단어의 끝인지 아닌지 체크
		boolean endOfword;
}

Node는 말 그대로 Trie자료구조의 각 노드를 의미합니다.

static을 붙여서 만드는 이유는 마지막에 main메서드 안에서 테스트를 하기 위함입니다.

 

그다음으로 Node를 사용할 Trie 자료구조 클래스를 만들어보겠습니다.

static class CodingNojam_Trie {
	
	// Trie자료구조를 생성할 떄 rootNode는 기본적으로 생성
	Node rootNode = new Node();

	// Trie에 문자열 저장
	void insert(String str) {
		// Trie자료구조는 항상 rootNode부터 시작 
		Node node = this.rootNode;
		
		// 문자열의 각 단어마다 가져와서 자식노드 중에 있는지 체크
		// 없으면 자식노드 새로 생성
		for(int i=0; i<str.length(); i++) {
			node = node.chiledNode.computeIfAbsent(str.charAt(i), key -> new Node());
		}
		// 저장 할 문자열의 마지막 단어에 매핑되는 노드에 단어의 끝임을 명시
		node.endOfword = true;
	}
	
	// Trie에서 문자열 검색
	boolean search(String str) {
		// Trie자료구조는 항상 rootNode부터 시작
		Node node = this.rootNode;
			
		// 문자열의 각 단어마다 노드가 존재하는지 체크 
		for(int i=0; i<str.length(); i++) {
			// 문자열의 각 단어에 매핑된 노드가 존재하면 가져오고 아니면 null
			node = node.chiledNode.getOrDefault(str.charAt(i), null);
			if(node == null) {
				// node가 null이면 현재 Trie에 해당 문자열은 없음
				return false;
			}
		}
		// 문자열의 마지막 단어까지 매핑된 노드가 존재한다고해서 무조건 문자열어 존재하는게 아님
		// busy를 Trie에 저장했으면, bus의 마지막 s단어에 매핑 된 노드는 존재하지만 Trie에 저장된건 아님
		// 그러므로 현재 노드가 단어의 끝인지 아닌지 체크하는 변수로 리턴
		return node.endOfword;
	}
}

Trie class는 문자열을 저장하기 위한 메서드와 검색을 위한 메서드를 내부에 같이 작성해주었습니다.

사실 이런 부분은 Trie class 내부에 작성하지 않고, 따로 빼서 작성하셔도 상관없습니다.

저는 공부를 하면서 여러 사람들의 구현 코드를 봤었는데 이러한 방식이 저한테 제일 잘 맞는 방법이어서 저는 Trie 클래스 내부에 기능적인 메서드들을 같이 작성해줍니다.

위의 코드들에 대한 설명은 주석에서 하고 있으니 자세한 설명은 따로 드리지 않겠습니다.

 

혹시나 computeIfAbsent()나 getOrDefault() 같은 메서드가 생소하시다면 제가 이전에 포스팅한 내용에서 이를 다루고 있으니 검색해서 읽어보시면 좋을 것 같습니다. (하나도 어렵지 않습니다!)

글 제목 : [Java] Map Interface의 유용한 메서드를 알아보자! (Java 8 기준)

 

구현은 다 끝났으니 실제로 main 메서드 안에서 테스트를 해보겠습니다.

public static void main(String[] args) {
		// Trie 자료구조 생성
		CodingNojam_Trie trie = new CodingNojam_Trie();
		
		// Trie에 문자열 저장
		trie.insert("kakao");
		trie.insert("busy");
		trie.insert("card");
		trie.insert("cap");
		
		// Trie에 저장 된 문자열 확인
		System.out.println(trie.search("bus"));		// false
		System.out.println(trie.search("busy"));    // true
		System.out.println(trie.search("kakao"));   // true
		System.out.println(trie.search("cap"));     // true
}

위의 코드를 보시면 bus라는 문자열은 저장하지 않았기 때문에 false를 리턴해주는 것을 확인할 수 있습니다.

이는 코드의 주석에서도 설명하고 있지만 busy 문자열을 저장하게 되면 s에 매핑되는 노드가 생성될 텐데 노드가 존재한다고 해서 단어가 저장된 것은 아니기 때문에 유의하셔야 합니다.

이를 확인하기 위해 우리는 Node 클래스에서 endOfWord라는 체크 변수를 사용하고 있습니다.

감사합니다.

---