Trie 트라이

어떤 문자열이 어떤 문자열들의 집합에 속하는지 알아내기 위해 단순히 모두 비교할 경우

O(문자열의 길이 x 문자열의 개수) 의 시간 복잡도를 가진다.

 

이 때 문자열을 효율적으로 저장하고 탐색하는 자료 구조가 Trie이다. 대충 O(N)

 

그냥 그림을 보면 이해가 쉽다. 아래와 같이 4개의 단어가 있다고 해보자.

Trie 자료 구조에 각 단어를 담아보면 아래와 같다.

Trie tree

 

 

 

 

트라이 자료구조는 주어진 문자열에 대해 앞 문자부터 하나씩 노드를 생성하면서 만들어진다.

 

Insert

1. 문자열에서 현재 문자를 확인

2. 현재 문자로 이루어진 노드가 존재한다면 → 그 노드를 탐색

존재하지 않는다면 → 새 노드를 생성

 

Find

1. 문자열에서 현재 문자를 확인

2. 자식 노드가 현재 문자인 노드가 있는지 확인, 없다면 return false

3. 문자열 끝까지 반복했을 때 위치한 노드가 끝 노드 이면(즉, 있는 단어이면) return true, 아니면 return false

 

C++ Trie 코드

응용도 가능하고 Insert와 Find가 있다.

#include <vector>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
struct TrieNode {
	int isWord = 0;
	TrieNode* children[26];

	TrieNode() {
		memset(children, 0, sizeof(children));
		isWord = false;
	}
	~TrieNode() {
		for (int i = 0; i < 26; ++i) {
			if (children[i]) {
				delete children[i];
			}
		}
	}

	void Insert(string& word, int index)
	{
		if (word.size() == index) {
			// 더 이상 문자가 없는 경우
			isWord = 1;
			return;
		}
		int curr = word[index] - 'A';
		if (children[curr] == NULL) {
			children[curr] = new TrieNode();
		}
		children[curr]->Insert(word, index + 1);
	}
	int Find(string& word, int index)
	{
		bool result = false;
		if (word.size() == index) {
			//해당 단어가 있는지?
			return isWord;
		}
		int curr = word[index] - 'A';
		if (children[curr]) return children[curr]->Find(word, index + 1);
		else return 0;	
	}
};
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	TrieNode root;
	string apple = "APPLE";
	root.Insert(apple, 0);

	string app = "APP";
	cout << root.Find(app, 0) <<"\n"; // 0
	cout << root.Find(apple, 0) << "\n"; // 1
	return 0;
}