트라이(Trie) - 1. 트라이 개념 및 노드 특징

트라이(Trie)

문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다.

하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다.

 

시간복잡도 : O(m) (m은 문자열 길이)

 

트라이 예

 

트라이(Trie) 특징

트라이(Trie) 노드

특징 1.

트라이의 각 노드는 문자와 자식 노드를 맵 형태로 가지고 있다.  -> Map<Character, TriNode>

예를 들어, 루트노드의 경우, 자식노드가 2개이므로

Key가 'b' 이고, Value에 왼쪽 자식 노드를 가지고 있으며,

Key가 'g' 이고, Value에는 오른쪽 자식 노드를 가지고 있다.

 

 

루트의 왼쪽 자식 노드도 마찬가지이다.

이 노드는 그림에서 보면 'b'를 가지고 있는 것처럼 보이지만, 사실은 특정 문자를 가지고 있는 것이 아니라 자식 노드의 문자를 Key로 하고 자식 노드를 Value로 하는 맵을 가지고 있다.

Map<Character, TriNode> childNodes

-> {'i', 왼쪽자식노드}, {'e', 오른쪽자식노드}

 

 

루트의 오른쪽 자식 노드도 마찬가지다.

그림에서 보면 'g'라는 문자 정보를 가지고 있을 것 같지만, 사실은

'i'가 Key이고, 왼쪽 자식 노드를 Value로 하고,

'o'가 Key이고, 가운데 자식 노드를 Value로 하고,

'r'가 Key이고, 오른쪽 자식 노드를 Value로 하는 맵을 가지고 있다.

Map<Character, TriNode> childNodes

-> {'i', 왼쪽자식노드}, {'o', 가운데자식노드}, {'r', 오른쪽자식노드}

 

 

 

특징 2.

트라이의 각 노드들은 해당 문자가 문자열의 마지막 문자인지 아닌지를 체크하는 변수(isLastChar)가 필요하다.

 

예를 들어서, "bird" 문자열의 마지막 문자는 'd' 이다.

그러면 'b', 'i', 'r' 문자는 마지막 문자가 아니므로 isLastChar = false 이고, 'd'는 isLastChar = true 가 된다.

 

그렇다면 왜 이렇게 마지막 문자인지 아닌지를 체크해줘야 할까?

1. 단어 포함 여부를 확인할 때

   찾으려는 단어의 마지막 문자의 isLastChar가 true 이면 해당 단어가 포함되어 있는 것이고,

   찾으려는 단어의 마지막 문자의 isLastChar가 false 이면 해당 단어가 포함되지 않은 것이다.

 

   예를 들어, 위의 예시에서 "beer" 이라는 단어가 포함되어있는지를 확인한다고 하자.

   "beer" 에서 문자 'r'에 도달할 때 'r'이 마지막 문자이므로 isLastChar = true 이다.

   그러므로 "beer"는 포함되어 있다.

 

   그러나 만약에 "bee" 라는 단어가 포함되어 있는지를 확인한다고 하자.

   트리의 루트부터 시작하여 마지막 'e'가 있는 노드까지 내려오면, "bee" 라는 단어가 있는 것처럼 보인다.

   하지만 "bee" 에서 마지막 'e'의 isLastChar는 false 이다.

  "bee" 는 "beer"라는 단어의 일부로써 존재하긴 하지만 "bee" 라는 단어 자체는 저장되어 있지 않기 

   때문이다. 만약에 isLastChar 라는 변수가 없다면, "bee"의 마지막 'e' 노드에 도달했을 때 "bee" 라는

   단어가 마치 존재하는 것처럼 착각할 수도 있다.

 

 

   그러므로, isLastChar를 통해 해당 단어가 실제 존재하는지 아니면 다른 단어의 일부로 존재하는지를

   체크할 수 있다.

 

2. 단어 삭제할 때

   특정 단어를 삭제하려고 할 때, 삭제하기 전에 먼저 해당 문자가 존재하는지를 확인해야 한다.

   위의 1번에서 이미 단어 존재여부를 확인할 때 isLastChar 의 필요성을 설명하였다.

 

   그렇다면 특정 단어가 존재한다고 가정하고 이 단어를 삭제한다고 하자.

   단어 삭제는 트리의 밑에서부터 위로 올라가며 노드들을 제거하는 과정으로 진행된다.

   그런데 노드를 제거하지 말아야 하는 상황이 두 가지가 있다.

 

   아래에서부터 노드를 제거하는 과정에서 중간에 있는 문자가 또 다른 단어의 마지막 문자일 수도 있다.

   이런 경우, 해당 노드를 제거하면 안된다.

   

   예를 들어, 위의 예시에서 "beer" 라는 단어를 삭제한다고 하자.

   마지막 문자인 'r' 부터 거슬러 올라가면서 노드를 하나씩 지운다.

   이 때 'b', 'e', 'e' 모두 isLastChar = false 이기 때문에 아무 무리 없이 제거할 수 있다.

 

   그런데 만약 아래 예시처럼 "bee" 라는 단어가 포함되어 있는 상태라고 하자.

   

   

   그러면 "beer" 에서 'r'을 제거하고, 'e' 가 있는 노드로 올라갔을 때, 'e' 노드를 제거하려고 봤더니

   "bee" 라는 단어가 존재하기 때문에 이 노드를 제거하면 "bee" 단어에 영향을 미치게 된다.

   따라서 'e' 노드의 isLastChar 가 true 이므로 해당 노드를 제거해서는 안된다.

 

 

 

이렇듯 1.단어 포함 여부를 확인할 때와 2.단어를 삭제할 때 isLastChar 가 필요한 이유를 살펴보았다.

 

 

정리하면, 트라이(Trie) 자료구조에서 트라이 노드는 자식노드의 정보를 저장하는 

Map<Character, TriNode> 과 마지막 문자 여부를 체크하는 isLastChar 를 가지고 있다.

 

아래는 트라이노드를 클래스로 구현한 소스코드이다.

static class TrieNode {

	private Map<Character, TrieNode> childNodes = new HashMap<>();
	private boolean isLastChar;

	public Map<Character, TrieNode> getChildNodes() {
		return childNodes;
	}

	public void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}

	public boolean isLastChar() {
		return isLastChar;
	}
}

 

위 소스코드는 아래 블로그를 참고하였다.

the-dev.tistory.com/3

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

 

이번에 트라이 및 노드의 특징에 대해 설명했으니, 다음에는 트라이의 동작(삽입, 포함여부, 삭제)에 대해 자세하게 다룰 것이다.