[자료구조] 트라이(Trie) c++

 트라이(Trie)란?

트라이는 문자열 검색을 빠르게 할 수 있도록 트리 형태로 문자열을 저장하는 자료구조이다. 
 
 
다음은 트라이의 예시이다.

트라이 예시

만약 apple, abc, apply, baby, basr이란 문자열들을 저장한다면 위와 같은 트리가 완성된다.
apple과 apply를 보면 두 문자열의 접두사 "appl"이 동일하고, 트리에서 해당 간선을 두 문자열이 공유한다.
 

트라이 예시

해당 트라이에서 apply를 찾으면 위와 같이 트리의 루트부터 탐색하며 문자열을 찾게된다.
 
 

---

트라이의 탐색 속도

선형적인 자료구조로 n개의 최대 길이가 m인 문자열을 저장할 때의 탐색 속도는 O(n×m)이다.
반면 트라이는 탐색, 삽입, 삭제 모두 문자열의 최대 길이(트리의 최대 깊이)만큼 O(m)의 시간이 걸린다. 이는 해시와 같은 속도로 굉장히 빠르다.
 

---

트라이 구현

트라이는 하위 노드를 정적 배열로 구현하는 방법과 맵을 통해 구현하는 방법이 있다. 일반적으로 map으로 구현하는 방법이 메모리 효율에서 더 좋다.

// 정적 배열을 통한 구현
struct Trie {
	bool isEnd;	
	Trie* child[26];
	Trie() {
		isEnd = false;
		for (int i = 0; i < 26; i++) child[i] = nullptr;
	}
};

// map을 통한 구현
struct Trie {
	bool isEnd;
	map<char, Trie*> child;
	Trie(){
    		isEnd = false;
    }
};

Trie *root = new Trie();

 
 
 

삽입

void insert(string str) {
	//루트 노드 가져오기
	Trie *cur = root;
	for (int i = 0; i < str.size(); i++) {
    	//대문자를 idx로 변경
		int x = str[i] - 65;
		// 간선이 있는지 확인
		if (cur->child[x]) { 
			cur = cur->child[x];
		}
		// 간선 없다면 새로 노드 만들고, 간선 연결
		else {
			cur->child[x] = new Trie();
			cur = cur->child[x];
		}
	}
	//문자열의 끝임을 알려줌
	cur->isEnd = true;
}

맵을 이용해 구현했다면, find함수를 통해 자식 노드가 있는지로만 변경하면 된다.
*문자열은 대문자로만 되어있는 경우로 가정하였다.
 
 

삭제

void remove(string str) {
	Trie* cur = root;
	//문자열 마지막 요소까지 이동시키기
	for (int i = 0; i < str.size(); i++) {
		int x = str[i] - 65;
		cur = cur->child[x];
	}
	//문자의 마지막이 아닌 것으로 변경
	cur->isEnd = false;
}

간선을 공유하는 경우에 다른 문자열에 영향을 줄 수 있어 물리적으로 삭제하진 않았다.
만약 물리적으로 삭제하고 싶다면, 리프 노드가 다른 문자열과 공유하는 간선이 없는 경우에 재귀를 통해 삭제해야한다.
 
 

조회

bool query(string str) {
	Trie* cur = root;
	//문자열의 마지막 요소로 이동시키기
	for (int i = 0; i < str.size(); i++) {
		int x = str[i] - 65;
		if (cur->child[x]) {
			cur = cur->child[x];
		}
		else {// 간선이 없는 경우 false
			return false;
		}
	}
	//문자열의 마지막인지 확인 후 리턴
	return cur->isEnd;
}

문자열의 마지막까지 내려가고, 마지막 문자인지만 확인하면 된다.
 
 

---

참고

트라이 with 메모리풀, 맵

#include <iostream>
#include <map>
using namespace std;
#define MAX 1000

struct Trie {
	bool isEnd;
	map<char, Trie*> child;
};

// 메모리 풀
Trie node_pool[MAX];
int p_cnt;

//노드 추가
Trie *new_node(){
	node_pool[p_cnt].isEnd = false;
    	// 메모리풀 재활용하는 경우에만 필요
	node_pool[p_cnt].child.clear();
	return &node_pool[p_cnt++];
}

Trie *root = new_node();

void insert(string str) {
	//루트 노드 가져오기
	Trie *cur = root;
	for (int i = 0; i < str.size(); i++) {
		char c = str[i];
		// 간선이 있는지 확인
		if (cur->child.find(c) != cur->child.end()) { 
			cur = cur->child[c];
		}
		else {
			cur->child[c] = new_node();
			cur = cur->child[c];
		}
	}
	//문자열의 끝임을 알려줌
	cur->isEnd = true;
}

void remove(string str) {
	Trie* cur = root;
	//문자열 마지막 요소까지 이동시키기
	for (int i = 0; i < str.size(); i++) {
		char c = str[i];
		cur = cur->child[c];
	}
	//문자의 마지막이 아닌 것으로 변경
	cur->isEnd = false;
}

bool query(string str) {
	Trie* cur = root;
	//문자열의 마지막 요소로 이동시키기
	for (int i = 0; i < str.size(); i++) {
		char c = str[i];
		if (cur->child.find(c) != cur->child.end()) {
			cur = cur->child[c];
		}
		else {// 간선이 없는 경우 false
			return false;
		}
	}
	//문자열의 마지막인지 확인 후 리턴
	return cur->isEnd;
}

int main() {

	return 0;
}

위 코드는 메모리 풀과 맵을 활용해 트라이를 구현한 코드이다.
메모리 풀을 사용하면 동적으로 할당하는 것보다 메모리면에선 비효율적일 수 있지만, 속도가 더 빠르다. 또한 새로 할당없이 재활용도 가능하다. 
대부분의 코딩 테스트는 제한 시간에 비해 제공하는 메모리는 굉장히 널널하므로, 위와 같은 방법으로 구현하는 것을 추천한다.
 

---

추천 문제

https://www.acmicpc.net/problem/14725
https://www.acmicpc.net/problem/5052
https://www.acmicpc.net/problem/9202
https://www.acmicpc.net/problem/19585