🔥[99클럽 코테 스터디] 15일차 TIL - Trie(트라이)

🔎Trie

Trie 자료구조는 문자열을 효율적으로 저장하고 검색하기 위해 설계된 트리 기반의 자료구조이다.

주로 문자열 검색, 자동 완성, 사전 구현 등 다양한 응용 프로그램에서 사용된다.

발음이 처음에는 '트리'였지만, 트리(Tree) 자료구조와 구분하기 위해 '트라이'로 바뀌었다고 한다.

원하는 원소를 찾기 위해 사용되는 이진 검색 트리에서는 원소를 찾는 데 $O(logN)$의 시간이 걸린다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이 만큼 시간이 걸리기 때문에, 원하는 문자열을 찾기 위해서는 $O(MlogN)$의 시간이 걸리게 된다.

이러한 단점을 해결하기 위한 문자열 특화 자료구조가 바로 이 트라이(Trie)이다.

🛠️작동 원리

다음 그림은 문자열 집합 {"apple", "april", "busy", "beer", "best"}를 트라이로 구현한 것이다.

트라이는 한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 파란색으로 나타낸 리프 노드는 문자열의 끝을 의미한다.

트라이는 문자열을 탐색하기 위한 자료구조이므로 문자열 탐색을 위해서는 다음 글자에 해당하는 노드를 타고 따라가면 된다.

예를 들어 "april"을 찾는다고 가정해보자.
a → ap → apr → apri → april의 순서로 탐색되므로 "april"의 모든 접두사들이 다 구해지게 된다.

🤔장단점

장점

• 문자열을 빠르게 찾을 수 있다.
• 문자열을 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색이 모두 $O(M)$만에 가능하다.

단점

• 필요한 메모리의 크기가 너무 크다.
• 문자열이 모두 알파벳 소문자로만 이루어진 경우라도 1 depth에 a~z까지 26개의 공간이 필요하게 된다.

---

💻구현

자바로 Trie를 구현하기 위해서는 자료구조인 Trie와 이를 구성할 TrieNode 클래스가 각각 필요하다.

TrieNode.java

TrieNode는 자식 노드 Map과 현재 노드가 마지막 글자인지 여부에 대한 정보를 가지고 있다.

public class TrieNode {
	// 자식 노드 Map
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// 마지막 글자인지 여부
	private boolean isLastChar;
	
}

이렇게 두 변수가 할당되었으니 이 변수에 접근할 수 있는 Getter와 Setter가 필요하다.

childNodes는 Trie차원에서 생성해 삽입할 것이기 때문에, Getter만 생성해 준다.
isLastChar는 추후 노드를 삭제하는 과정에서 변경이 필요하기 때문에, Getter와 Setter를 둘 다 생성해 준다.

public class TrieNode {
	// 자식 노드 Map
	private Map<Character, TrieNode> childNodes = new HashMap<>();
	// 마지막 글자인지 여부
	private boolean isLastChar;
	
	// 자식 노드 맵 Getter
	Map<Character, TrieNode> getChildNodes() {
		return this.childNodes;
	}
	// 마지막 글자인지 여부 Getter
	boolean isLastChar() {
		return this.isLastChar;
	}
	// 마지막 글자인지 여부 Setter
	void setIsLastChar(boolean isLastChar) {
		this.isLastChar = isLastChar;
	}
}

Trie.java

Trie는 기본적으로 빈 문자열을 가지는 루트 노드만 가지고 있다.

public class Trie {
	private TrieNode rootNode; // 루트 노드
}

자식 노드는 곧 나올 insert메서드를 통해 문자를 입력함으로써 생성될 것이다.

우선, Trie가 생성되면 rootNode가 생성될 수 있도록 생성자를 통해 rootNode를 생성해 준다.

public class Trie {
	private TrieNode rootNode; // 루트 노드
    
    // 생성자
    Trie() {
    	rootNode = new TrieNode();
    }   
}

insert

insert 메서드에서는 입력받은 단어의 각 알파벳을 계층 구조의 자식 노드로 만들어 넣는 과정을 거친다.
이 때, 이미 같은 알파벳이 존재하면 공통 접두어 부분까지는 생성하지 않는다.
즉, 해당 계층 문자의 자식 노드가 존재하지 않을 때만 자식 노드를 생성해준다.

예를 들어, "apple"이 들어있는 Trie에 "april"을 넣을 때, "ap"는 중복이므로 "a → p"노드 아래 "→ r → i → l"만 추가로 자식 노드를 생성해 주면 되는 것이다.

그리고 리프 노드에서는 마지막 문자라는 것을 표시하기 위해 setIsLastChar(true)를 해준다.

void insert(String word) {
	TrieNode thisNode = this.rootNode;

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

contains

특정 단어가 Trie에 존재하는 지 확인하기 위해서는 다음 조건을 만족시켜야 한다.

• 루트 노드부터 순서대로 알파벳이 일치하는 자식 노드들이 존재할 것

• 해당 단어의 마지막 글자에 해당하는 노드의 isLastChar가 true일 것

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

delete

마지막으로 단어를 삭제하는 메서드이다.
일단, contains 메서드처럼 주어진 단어를 찾아 하위 노드로 단어 길이만큼 내려간다.
여기서 주의할 점은 노드들이 부모 노드의 정보를 가지고 있지 않기 때문에, 하위 노드로 내려가며 삭제 대상 단어를 탐색하고, 다시 올라오며 삭제하는 과정이 구현되어야 한다는 점이다.

delete 메서드는 아래의 조건을 만족해야 한다.

• 자식 노드를 가지고 있지 않아야 한다.
• 삭제를 시작하는 첫 노드는 isLastChar이 true여야 한다.
• 삭제를 진행하는 중에는 isLastChar이 false여야 한다.

void delete(String word) {
	delete(this.rootNode, word, 0); 
}
	
private void delete(TrieNode thisNode, String word, int index) {
		
	char character = word.charAt(index);
            
	TrieNode childNode = thisNode.getChildNodes().get(character);
	index++;
    
	if(index == word.length()) {
		childNode.setIsLastChar(false);

		// 삭제 대상 언어의 제일 끝으로써 자식 노드가 없으면(이 단어를 포함하는 더 긴 단어가 없으면) 삭제 시작
		if (childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(character);
	}
    else {
		delete(childNode, word, index);
		// 삭제 중, 자식 노드가 없고 현재 노드로 끝나는 다른 단어가 없는 경우 이 노드 삭제
		if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
			thisNode.getChildNodes().remove(character);
	}
}

---

💻Reference
[JAVA/자료구조] 트라이(Trie) 개념, 직접 구현하기