[자료구조] 트라이(Trie)의 구현 (JAVA)

이번 포스팅에서는 문자열 데이터를 다루기에 최적화된 자료구조중 하나인 트라이에 대해 다뤄보고자 한다.

 

먼저 위키백과를 통해 기본 정의부터 알아보도록 하겠다.

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85) 

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

 

정의를 보면 탐색트리의 일종으로 동적집합이나 연관배열을 저장하는데 사용되는 트리 자료구조라고

명시되어있다.

 

동적집합이란 특정한 값들을 저장하는 추상 자료형으로 원소들의 삽입, 삭제, 그리고 쿼리연산(탐색등)이

가능하단 특징을 갖고 있다.

 

따라서 동적집합, 연관배열을 갖는 탐색트리를 트라이라고 생각하면 되겠다.

 

이런 트라이는 크게 3종류의 활용이 가능하다.

 

1. 자동완성

주어진 접두사를 활용해 자동완성 기능을 만들 수 있다.

 

2. 정렬

키 집합으로 하위노드가 정렬된 트라이로 생성한다면

전위순회를 통해 사전순으로 저장된 데이터를 출력할수 있다.

 

3. 전문검색

트라이의 특수한 형태로 구현된 접미사트리는

빠른 전문(full-text) 검색에 활용하기 위해 모든 접미사를 색인하는데 이용할 수 있다.

 

 

 

---

 

그렇다면 트라이를 그림을 통해 삽입과정을 살펴보도록하겠다.

 

간단한 영어사전을 하나 생각해보도록 하겠다.

 

단어 apple, auto, ball 를 삽입한다면

 

다음과 같은 과정을 거치게 된다.

 

1. 문자열의 첫번째 문자부터 루트의 자식노드의 키로 저장한다.

2. 자식노드에서는 다음 문자를 자식노드의 키로 저장한다.

3. 문자열이 끝나는 시점까지 반복후 마지막노드에서는 문자열을 저장한다.

 

이를 도식화 하면 다음과 같은 모양으로 생각할 수 있을 것이다.

 

apple의 삽입과정

 

 

이 과정을 반복해 위에서 언급한 단어를 모두 저장한 트라이를 간단히 표현하면

다음과 같은 그림이된다.

 

 

 

검색을 하고 싶다면 같은 과정을 거쳐 탐색하기만 하면 된다.

찾으려는 단어의 마지막노드에서 데이터가 존재한다면 해당 값을 가져오면 되고

없다면 존재하지 않는 데이터인 셈인것이다.

 

 

그럼 바로 코드로 구현 해보도록 하겠다.

 

먼저 트라이의 노드부터 클래스로 선언해주도록 하겠다.

 

각 노드는 필드로 노드의 키, 그리고 데이터, 자식노드를 갖는다.

 

class TrieNode {
	private char key;
	private String data;
	private TrieNode[] child;
    
}

 

현재 구현할 트라이는 영어사전을 구현해볼것이므로 영소문자로만 입력을받는다 가정하고

구현해보도록하겠다.

 

즉 각 노드의 필드로 갖는 자식노드의 배열은 길이 26으로 갖게될것이다.

 

따라서 생성자에서는 배열의 길이를 할당하고 키값을 저장할수 있도록 해주겠다.

 

	TrieNode(char key){
		this.key = key;
		child = new TrieNode[26];
	}

 

다음은 삽입시 자식노드 배열에 새로운 노드 객체를 생성해 저장할수 있도록하는

add 메소드이다. 이때 자시노드 배열에서 이미 객체가 존재한다면 객체를 생성할 필요가 없다.

인자로 받는 키값으로 노드에 대한 메모리를 할당 후 인자로 받은 키값이 가리키는

자식노드로 리턴해줄수 있도록 했다.

 

	TrieNode add(char key) {
		if(child[key - 'a'] == null) {
			child[key - 'a'] = new TrieNode(key);			
		}
		return child[key - 'a'];
	}

 

 

그리고 검색시 키값이 가리키는 노드를 리턴해줄수 있는 find 메소드와

데이터를 저장하고 가져오는 getter, setter 또한 만들어 준다.

 

	TrieNode find(char key) { return child[key - 'a']; }
	
	void setData(String data) { this.data = data; }
	String getData() { return data; }

 

 

이제 트라이를 선언해 보도록하겠다.

 

 

트라이는 트리형 자료구조이므로 기준이 되는 루트노드를 필드로 두고

생성자에서 루트노드에 대해 객체를 할당할 수 있도록 한다.

 

public class TrieImpl {

	private TrieNode root;
	
	TrieImpl(){
		root = new TrieNode('\0');
	}
}

 

 

현재 구현하는건 삽입과 검색만 구현해 보려하므로

 

삽입 메소드 그리고 검색메소드를 각각 선언하도록 하겠다.

 

먼저 삽입메소드는 삽입하려는 문자열을 인자로 받고

문자열의 길이, 그리고 문자열의 첫번째 문자부터 루트노드에 저장 후 재귀를 통해

입력받은 문자열의 끝까지 트라이에 저장할 재귀메소드를 호출해주도록 하겠다.

 

	void insert(String str) {
		int size = str.length();
		char key = str.charAt(0);
		insertProcess(root.add(key),str,size,1);
	}
	
	private void insertProcess(TrieNode node, String str, int size, int idx) {
		if(size == idx) {
			node.setData(str);
			return;
		}
		char key = str.charAt(idx);
		insertProcess(node.add(key),str,size,idx + 1);
	}

 

 

조금 더 부연 설명을 하자면 재귀 호출 메소드에서는 문자열의 길이와 진행중인 재귀에서

현재 인자로 받은 문자열의 n 번째 문자와 일치하면 모든 문자열의 삽입이 완료되었단 의미이므로

현재 노드에 데이터를 저장후 리턴해주도록 한다.

 

 

다음은 검색 메소드 부분이다.

검색시 인자로 받은 문자열이 트라이에 존재한다면 true, 아니라면 false로 리턴해주어

문자열에 대한 검사를 할 수 있도록 한다.

 

역시 삽입과정과 마찬가지로 문자열의 첫번째문자부터 루트에서 재귀호출을 통해

찾고자 하는 문자열이 존재하는지 찾을 수 있도록 한다.

 

	boolean search(String str) {
		int size = str.length();
		if(size == 0) return false;
		return searchProcess(root,str,size,0);
	}
	
	private boolean searchProcess(TrieNode node, String str, int size, int idx) {
		if(size == idx) return node.getData() != null;
		TrieNode child = node.find(str.charAt(idx));
		if(child == null) return false;
		return searchProcess(child,str,size,idx + 1);
		
	}

 

 

이제 트라이의 구현이 완료되었으니

위에서 그림으로 언급한 예제로 한번 테스트 해보도록하겠다.

 

apple, auto, ball 단어를 삽입 후 문자열 a, apple 이 존재하는가 확인 해보는 테스트이다.

 

	public static void main(String[] args) {
		String[] word = { "apple" , "auto" , "ball" };
		TrieImpl trie = new TrieImpl();
		for(int i = 0; i < 3; i++) {
			trie.insert(word[i]);
		}
		
		System.out.println(trie.search("a"));
		System.out.println(trie.search("apple"));
	}

 

 

실행결과)

 

 

 

 

아래는 코드의 전문이다.

 

package impl;

public class TrieImpl {
	
	private TrieNode root;
	
	TrieImpl(){
		root = new TrieNode('\0');
	}
	
	void insert(String str) {
		int size = str.length();
		char key = str.charAt(0);
		insertProcess(root.add(key),str,size,1);
	}
	
	private void insertProcess(TrieNode node, String str, int size, int idx) {
		if(size == idx) {
			node.setData(str);
			return;
		}
		char key = str.charAt(idx);
		insertProcess(node.add(key),str,size,idx + 1);
	}
	
	boolean search(String str) {
		int size = str.length();
		if(size == 0) return false;
		return searchProcess(root,str,size,0);
	}
	
	private boolean searchProcess(TrieNode node, String str, int size, int idx) {
		if(size == idx) return node.getData() != null;
		TrieNode child = node.find(str.charAt(idx));
		if(child == null) return false;
		return searchProcess(child,str,size,idx + 1);
		
	}
	
	public static void main(String[] args) {
		String[] word = { "apple" , "auto" , "ball" };
		TrieImpl trie = new TrieImpl();
		for(int i = 0; i < 3; i++) {
			trie.insert(word[i]);
		}
		
		System.out.println(trie.search("a"));
		System.out.println(trie.search("apple"));
	}

}

class TrieNode {
	private char key;
	private String data;
	private TrieNode[] child;
	
	TrieNode(char key){
		this.key = key;
		child = new TrieNode[26];
	}
	
	TrieNode add(char key) {
		if(child[key - 'a'] == null) {
			child[key - 'a'] = new TrieNode(key);			
		}
		return child[key - 'a'];
	}
	
	TrieNode find(char key) { return child[key - 'a']; }
	
	void setData(String data) { this.data = data; }
	String getData() { return data; }
}

 

 

 

---

 

 

트라이는 탐색하거나, 삽입할 문자열의 길이가 m이라면 O(m)의 시간 복잡도로 

연산속도에서 강점을 갖는 자료구조 이므로 반드시 구현해보고 응용한다면

신속하고 좋은 품질의 코드를 구현하는데 조금 더 도움이 될것이다.