트라이(Trie)

트라이란?

문자열에 특화된 자료구조

문자열 집합을 표현하는 트리 자료구조

원하는 원소를 찾는 작업을 O(n)에 해결할 수 있는 자료구조

우선 문자열 5개 {"blog", "he", "her", "crocus", "cross"}를 가지고 있다고 생각해보자.

 

트라이는 이때 위와 같이 그림을 형성하게 된다.

 

사실상 트라이는 그림으로 보면 바로 이해가 되리라 생각이 든다.

 

루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고,

 

루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다.

 

her은 h -> he -> her이 되고, her의 접두사에는 h, he가 존재한다.

 

이때 he는 문자열에서 나타난 종류 중 하나이다. 

 

즉, her이 he를 포함하는 것도 트라이에서 알 수 있게 된다.

 

이러한 내용들 때문에 트라이는 접두사 트리(Prefix Tree) 라고도 불린다.

 

Java로 구현한 Trie를 보면서 이해를 더 해보자.

 

아래에는 Java 8기반의 collection api가 사용된다. 혹시 모른다면 이곳에서 조금 보고 오면 좋을것같다.

dkwjdi.tistory.com/169

[Java8] 새로운 collection api

 

클래스 생성

우선 자바로 Trie자료구조를 구현하기 위해서는 

자료구조인 Trie 클래스와 이를 구성할 TrieNode 클래스가 필요하다. 

 

우선 TrieNode클래스부터 확인해보자

static class TrieNode{
		HashMap<Character, TrieNode> childNodes = new HashMap<>(); //자식노드맵
		boolean isLastChar; //마지막 글자인지 확인
		
		public HashMap<Character, TrieNode> getChildNodes() { //자식노드 게터
			return childNodes;
		}
		public boolean isLastChar() { //마지막 글자인지 확인 게터
			return isLastChar;
		}
		public void setLastChar(boolean isLastChar) { //마지막 글자 확인 세터
			this.isLastChar = isLastChar;
		}
	}

 

이어서 Trie 클래스도 한번 보자

	static class Trie{
		TrieNode rootNode;
		
		Trie(){
			rootNode = new TrieNode(); //생성자
		}
   }

 

이제 메서드를 한번 구현해보자. 여기서는 insert, contains 두개만 구현하겠다.

 

1. insert

void insert(String word){
	TrieNode thisNode=this.rootNode;
			
	for(int i=0; i<word.length(); i++) { //문자열의 길이만큼
		thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), key->new TrieNode());
		//thisNode는 계속해서 아래로 향한다.
	}
	thisNode.setLastChar(true); //마지막 글자 체크
}

 

2. contains

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();	
    }

참고

https://www.crocus.co.kr/1053

the-dev.tistory.com/3