트라이(Trie) - 2. 삽입, 포함 여부, 삭제

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

 

위의 글에서는 트라이 개념, 트라이 노드 특징(Map<Character, TriNode>, isLastChar)에 대해 설명했었다.

이번에는 트라이(Trie)의 동작 1. 단어 삽입 2. 단어 포함 여부 3. 단어 삭제 에 대해서 자세하게 다룰 것이다.

 

트라이

위의 트라이 그림에서 포함되어 있는 단어는 

"bird", "big", "beer", "girl", "god", "grow" 여섯 가지이다.

 

트라이노드(TrieNode)의 클래스는 아래와 같이 구현할 수 있다.

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

 

단어 삽입

트라이(Trie)에 새로운 단어를 삽입하는 경우다.

루트부터 시작하여서 단어의 첫번째 문자부터 트리에 포함되어 있는지 확인한다.

• 특정문자 노드가 트리에 포함되어 있으면, 자식 노드로 이동하여 다음 문자 노드가 있는지 확인한다.

• 특정문자 노드가 트리에 포함되어 있지 않으면, 새로운 자식 노드를 생성한다.

 

예를 들어 위의 트라이 그림에서 "bed" 라는 단어를 삽입한다고 하자.

루트 노드의 자식 노드들 중에 'b' 가 있는지 확인한다. 즉, 루트 노드가 가지고 있는 Map 에서

'b'를 Key로 가지고 있는 노드가 존재하는지를 확인해야 한다. 

 

아래 그림을 보면 자식 노드 중에 'b'가 존재한다.

그러므로 루트 노드에서 왼쪽 자식 노드로 이동한다.

 

 

그 다음, 'b'의 자식 노드 중에 "bed" 의 두번째 문자인 'e'가 있는지 확인해본다.

즉, 현재 노드의 Map 중에서 'e'를 Key로 가진 자식 노드가 존재하는지 확인하는 것이다.

아래 그림에서 'b'의 자식 노드 중에 'e' 노드가 존재하므로 자식 노드로 이동한다.

 

 

그 다음으로는 "bed"의 마지막 문자인 'd' 가 자식 노드에 포함되어있는지 확인한다.

현재 노드의 Map에 'd'를 Key로 하는 자식 노드가 있는지를 확인한다.

현재 노드에서 'd'를 Key로 하는 자식 노드가 없다.

그러므로 현재 노드에 자식 노드를 새로 추가해야 한다.

즉, 현재 노드의 Map에 'd'를 Key로 하는 새로운 노드를 생성한다.

 

 

insert 소스코드 :

// 단어 삽입
public 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());
	}
	node.setIsLastChar(true);
}

 

 

단어 포함 여부

루트 노드부터 시작하여 아래로 내려가면서 단어의 첫번째 문자부터 트리에 포함되는지를 확인한다.

 

• 마지막 문자가 아니라면, 현재 노드가 다음 문자를 Key로 하는 자식 노드를 가지고 있어야한다.

• 마지막 문자라면, 마지막 노드의 isLastChar가 true 이어야 한다. isLastChar = false 이면 찾으려는 단어에 해당하는 모든 노드가 트리에 존재한다고 하여도 단어가 포함되어있다고 볼 수 없다.

 

"bee" 단어의 포함여부 확인하기

루트 노드의 Map 에서 'b'를 Key로 하는 자식 노드가 존재하는지 살펴본다.

'b'를 Key로 하는 자식 노드가 존재하므로 루트 노드에서 왼쪽 자식 노드로 이동한다.

 

Map에 다음 문자인 'e' 를 Key로 하는 자식 노드가 있는지 확인한다.

역시 존재하므로, 'b' 에서 자식 노드인 'e'로 이동한다.

 

 

현재 노드에서 "bee" 의 마지막 문자인 'e'를 Key로 하는 자식 노드를 가지고 있는지 확인한다.

가지고 있으므로 자식 노드로 이동할 수 있다.

"bee"의 마지막 문자 노드까지 도착했다.

이제 마지막 노드의 isLastChar가 true 인지 확인해야 한다. 

그런데 마지막 노드의 isLastChar = false 이므로 "bee"는 포함되어 있지 않다고 봐야한다.

 

contain 소스코드 : 

// 단어 포함 여부 확인
public boolean contain(String word) {

	TrieNode thisNode = this.rootNode;

	for (int i = 0; i < word.length(); i++) {
		thisNode = thisNode.getChildNodes().get(word.charAt(i));

		if (thisNode == null)
			return false;
	}

	return thisNode.isLastChar();
}

 

 

 

단어 삭제

단어를 삭제하는 과정은 조금 복잡하다.

단어 삭제는 재귀를 통해 아래에서부터 위로 올라가면서 단어에 포함된 문자의 노드를 제거한다.

 

• 현재 노드가 마지막 문자라면,

      - isCharLast = true 이어야 한다.

        isCharLast = false 이면, 삭제하려는 단어가 존재하지 않다는 뜻이기 때문이다.

        존재하지 않은 단어를 삭제할 수는 없다.

 

      - 자식 노드가 없어야 한다.

        만약 현재 노드에 자식 노드가 존재한다면, 현재 노드를 삭제함으로써 현재까지의 문자들을 포함하는

        다른 문자에까지 영향을 미칠 수 있다.

 

• 현재 노드가 마지막 문자가 아니라면(아래에서 올라오면서 이미 자식 노드를 제거했음)

   

      - isCharLast = false 이어야 한다.

        isCharLast = true 이면, 지금 문자를 마지막 문자로 하는 다른 단어가 존재한다는 뜻이다.

        그러므로 현재 노드를 제거하면 다른 단어에 영향을 미칠 수 있다.

 

      - 자식노드가 없어야 한다.

        현재 노드는 아래에서 노드를 제거하면서 올라오다가 도달한 상태이다.

        그렇기 때문에 만약 오직 한 단어에만 속해있는 문자라면 올라오는 과정에서 자식 노드가 다

        제거되므로 자식 노드가 하나도 없어야 한다. 

        즉, 현재 노드에 도달했는데 여전히 자식 노드가 존재한다는 의미는 현재 문자를 필요로 하는

        다른 단어가 존재한다는 뜻이다.

 

 

예를 들어, "beer" 을 제거하는 경우를 보자.

 

가장 아래인 'r'가 있는 노드부터 시작한다.

'r'이 있는 노드는 가장 마지막 노드이므로 isLastChar = true 이다. 그리고 자식 노드도 없다.

그러므로 현재 노드를 제거한다.

 

 

 

부모 노드로 올라오면, 아래에서 이미 자식 노드가 제거되었으므로 'e' 를 나타내는 현재 노드는 자식 노드가 하나도 없다. 그리고 "bee" 라는 단어가 포함되어 있지 않으므로 현재 노드는 마지막 문자가 아니기 때문에 isLastChar = false 이다.

따라서 현재 노드를 삭제해도 무방하므로 제거하고, 부모 노드로 올라온다.

 

 

 

아래에서 올라오면서 "beer"에 포함되는 자식 노드를 제거하였다.

그런데 'e'에 해당하는 현재 노드를 보면 자식이 아직 남아있음을 확인할 수 있다. 'd'를 Key로 하는 자식 노드가 있다.

이는 "be" 가 "beer" 뿐만 아니라 "bed"에도 포함되어 있기 때문이다.

따라서 현재 노드를 제거하게 되면 "bed" 단어에 영향을 미칠 수 있기 때문에 제거하면 안된다.

 

 

 

 

delete 소스코드 : 

// 단어 삭제
public boolean delete(String word) {

	return delete(rootNode, word, 0);
}

public boolean delete(TrieNode thisNode, String word, int index) {

	char ch = word.charAt(index++);
	TrieNode childNode = thisNode.getChildNodes().get(ch);

	// 단어의 마지막 문자를 체크하는 경우 : base case
	if (index == word.length()) {

		// 찾으려는 단어가 없는 경우
		// 현재가 마지막 문자인데 isLastChar이 false라는건 찾는 단어가 없다는 뜻
		if (!childNode.isLastChar())
			return false;

		childNode.setIsLastChar(false);

		// 현재 단어가 마지막인 경우
		if (childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(ch);

		return true;
	}

	// 재귀함수 호출
	if (delete(childNode, word, index)) {

		if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(ch);

		return true;
	}
	return false;
}

 

 

트라이(Trie)의 전체 소스코드이다.

static class Trie {

	private TrieNode rootNode;

	Trie() {
		rootNode = new TrieNode();
	}

	// 단어 삽입
	public void insert(String word) {

		TrieNode node = this.rootNode;

		for (int i = 0; i < word.length(); i++) {
			node = node.getChildNodes().computeIfAbsent(word.charAt(i), key -> new TrieNode());
		}
		node.setIsLastChar(true);
	}

	// 단어 포함 여부 확인
	public boolean contain(String word) {

		TrieNode thisNode = this.rootNode;

		for (int i = 0; i < word.length(); i++) {
			thisNode = thisNode.getChildNodes().get(word.charAt(i));

			if (thisNode == null)
				return false;
		}

		return thisNode.isLastChar();
	}

	// 단어 삭제
	public boolean delete(String word) {

		return delete(rootNode, word, 0);
	}

	public boolean delete(TrieNode thisNode, String word, int index) {

		char ch = word.charAt(index++);
		TrieNode childNode = thisNode.getChildNodes().get(ch);

		// 단어의 마지막 문자를 체크하는 경우 : base case
		if (index == word.length()) {

			// 찾으려는 단어가 없는 경우
			// 현재가 마지막 문자인데 isLastChar이 false라는건 찾는 단어가 없다는 뜻
			if (!childNode.isLastChar())
				return false;

			childNode.setIsLastChar(false);

			// 현재 단어가 마지막인 경우
			if (childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(ch);

			return true;
		}

		// 재귀함수 호출
		if (delete(childNode, word, index)) {

			if (!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
				thisNode.getChildNodes().remove(ch);

			return true;
		}
		return false;
	}
}

	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 : 자바로 구현하기