• Trie 란 문자열의 집합을 표현하는 트리 자료 구조로, 문자열 특화 자료 구조 대표적으로 자동완성
• Tire 왜? 사용하지?
  • 정수나 실수형 변수는 그 크기가 항상 정해져 있기 때문에 비교를 하는 경우 상수 시간 O(1) 이 걸린다고 가정해도 되는 반면, 문자열 변수는 비교 시 최악의 경우 문자열의 길이에 비례하는 시간이 걸리게 된다.
  • 이와 같이 정수나 실수 Key 에 대해서는 훌륭하게 동작하는 탐색 자료 구조들도 문자열을 Key 로 사용할 때는 시간이 소요 될 수 있다.
  • 원소 간의 비교를 상수 시간에 할 수 있을 때는 N 개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾으려면 O(log N) 번의 비교를 할 수 있지만 문자열의 비교에는 그 길이에 비례하는 시간이 걸리므로 문자열 최대 길이 M 을 곱한 O(M log N) 이 최종 시간 복잡도가 된다.
  • 위와 같은 문제를 해결하기 위해 고안된 문자열 특화 자료구조가 Trie 이다. Tire 는 트리 자료 구조로 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있다.

Trie 동작 과정

Trie 구현하기

// 전체 코드
class TrieNode {
	Map<Character, TrieNode> childNode = new HashMap<>();
	boolean end;

	public void insert(String word) {
		TrieNode trieNode = this;
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);

			trieNode.childNode.putIfAbsent(c, new TrieNode());
			trieNode = trieNode.childNode.get(c);

			if (i == word.length() - 1) {
				trieNode.end = true;
				return;
			}
		}
	}

	public boolean contains(String word) {
		TrieNode trieNode = this;
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);

			TrieNode node = trieNode.childNode.get(c);
			if (node == null) {
				// 문자가 존재하지 않음
				return false;
			}
			trieNode = node;
		}
		// 해당 단어로 종료하는 문자가 있는 경우 false
		return trieNode.end;
	}

}