Trie 정리

Trie 자료구조는 Tree와 유사하지만, element 개별로 트리를 구성하는 것이 아닌, 공통 prefix를 기준으로 tree를 구성한다. 

 

대표적인 Trie 예시는 string 간의 공통 substring 검색, 검색엔진에서 검색어 유무 확인, 이더리움의 state 저장에 사용되는 merkle patricia trie 등이 있다.

 

Trie 예시 : 알파벳 소문자로만 이루어진 경우

 

입력 : apple, app, banana, bbb, ccc, cat

 

 

root를 기준으로 새로운 문자열 삽입 시, char 단위로 null이 아닌 곳을 따라 가다가 null 인 지점을 만나게 되면 해당 노드부터 한 글자씩 노드를 추가로 생성하면 된다. 

 

입력된 문자열이 Trie에 존재하는 지 여부의 경우, 마찬가지로 Trie 내를 탐색하다가 문자열 끝까지 도달하지 못했지만 null을 만나게 되면 해당 입력 문자열은 존재하지 않는 경우이다. 

 

---

Trie 구현 C++

 

(알파벳 소문자로만 이루어진 경우)

 

트라이 생성 

각 알파벳에 해당하는 노드에 null을 부여하여 root 노드를 만든다.

const int ALPHABET_SIZE = 26;

struct TrieNode {
	TrieNode* children[ALPHABET_SIZE]; // 자식 노드 (알파벳 소문자만 있다고 가정) 
	bool isEnd; // 해당 노드가 단어 끝인지 여부  
};

TrieNode* createNode()
{
	// 신규 노드 생성 
	TrieNode *node = new TrieNode;
	node->isEnd = false;
	
	for(int i = 0; i < ALPHABET_SIZE; i++)
		node->children[i] = nullptr;
	
	return node;
}

 

문자열 입력

각 문자열을 char 단위로 체크하면서 해당 char에 대해 아직 null인 경우, 신규 노드를 생성한다.

void insert(TrieNode *root, const char str[])
{
	TrieNode *node = root;
	
	int idx;
	for(int i = 0; i < strlen(str); i++) {
		idx = str[i] - 'a';
		
		// 해당 알파벳이 자식 노드에 없음 
		if(node->children[idx] == nullptr)
			node->children[idx] = createNode();
		
		node = node->children[idx];
	}
	
	// 마지막 글자에 대한 node는 끝으로 처리  
	node->isEnd = true;
}

 

문자열 찾기

(단순 true, false가 아닌, 입력된 문자열의 몇 번째까지 검색되는 지 리턴, 첫 글자부터 검색 안 될 시 -1)

문자열을 char 단위로 체크하면서 null을 만나게 되는 경우 직전 index를 리턴한다. 

int search(TrieNode *root, const char str[])
{
	// str의 어느 부분까지 일치하는 지 리턴 (0부터 시작) 
	// 처음부터 일치하지 않으면 -1 리턴 
	 
	TrieNode *node = root;
	
	int idx;
	for(int i = 0; i < strlen(str); i++) {
		idx = str[i] - 'a';
		
		// str에 해당하는 부분 없을 때 -1 리턴  
		if(node->children[idx] == nullptr)
			return i - 1;
		
		node = node->children[idx];
	}
	
	// 다 일치하는 경우  
	return strlen(str) - 1; 
}

 

트라이 메모리 해제

메모리 할당을 해주었으므로 해제는 아래와 같이 recursive하게 진행한다.

void deleteTrie(TrieNode *root)
{
	if(root == nullptr)
		return;
	for(int i = 0; i < ALPHABET_SIZE; i++)
		if(root->children[i] != nullptr)
			deleteTrie(root->children[i]);
			
	delete root;
	return;
}

---

전체 코드

#include <iostream> 
#include <cstring>

using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode {
	TrieNode* children[ALPHABET_SIZE]; // 자식 노드 (알파벳 소문자만 있다고 가정) 
	bool isEnd; // 해당 노드가 단어 끝인지 여부  
};

TrieNode* createNode()
{
	// 신규 노드 생성 
	TrieNode *node = new TrieNode;
	node->isEnd = false;
	
	for(int i = 0; i < ALPHABET_SIZE; i++)
		node->children[i] = nullptr;
	
	return node;
}

void insert(TrieNode *root, const char str[])
{
	TrieNode *node = root;
	
	int idx;
	for(int i = 0; i < strlen(str); i++) {
		idx = str[i] - 'a';
		
		// 해당 알파벳이 자식 노드에 없음 
		if(node->children[idx] == nullptr)
			node->children[idx] = createNode();
		
		node = node->children[idx];
	}
	
	// 마지막 글자에 대한 node는 끝으로 처리  
	node->isEnd = true;
}

int search(TrieNode *root, const char str[])
{
	// str의 어느 부분까지 일치하는 지 리턴 (0부터 시작) 
	// 처음부터 일치하지 않으면 -1 리턴 
	 
	TrieNode *node = root;
	
	int idx;
	for(int i = 0; i < strlen(str); i++) {
		idx = str[i] - 'a';
		
		// str에 해당하는 부분 없을 때 -1 리턴  
		if(node->children[idx] == nullptr)
			return i - 1;
		
		node = node->children[idx];
	}
	
	// 다 일치하는 경우  
	return strlen(str) - 1; 
}

void deleteTrie(TrieNode *root)
{
	if(root == nullptr)
		return;
	for(int i = 0; i < ALPHABET_SIZE; i++)
		if(root->children[i] != nullptr)
			deleteTrie(root->children[i]);
			
	delete root;
	return;
}

int main()
{
	TrieNode *root = createNode();
	
	insert(root, "apple");
	insert(root, "app");
	insert(root, "banana");
	insert(root, "bbb");
	insert(root, "ccc");
	insert(root, "cat");
	
	cout << "index of char to retrieve the word\n";
	cout << "word list : \n";
	cout << "apple, app, banana, bbb, ccc, cat\n"; 
	
	cout << "apple : " << search(root, "apple") << "\n";
	cout << "ddd : " << search(root, "ddd") << "\n";
	cout << "ban : " << search(root, "ban") << "\n";
	cout << "cccc : " << search(root, "cccc") << "\n";
	
	deleteTrie(root);
}

 

결과