[알고리즘] 트라이 (Trie) 자료구조 개념 및 구현 (C++)

트라이 (Trie) 자료구조란?

문자열 검색에 최적화된 트리 형태의 자료구조이다.

상위 문자가 하위 문자들의 부모 노드가 되는 트리 구조를 가지고 있다.

'tree', 'trie', 'trim' 이렇게 3개의 문자열을 포함하는 트라이의 예시를 보자.

 

그림에서 보는 것과 같이,

't' 밑에 'r' 이 하위 노드로 들어가 있고,

'r' 밑에 'i' 와 'e' 가 하위 노드로 들어가 있는 것을 볼 수 있다.

이와 같은 구조를 가지고 있기 때문에, 길이 m의 특정 문자열이 존재하는지 판단하는 것이 O(m) 시간으로 가능하다.

 

 

 

 

트라이에 필요한 기능

트리 구조에 익숙한 분들이라면 위의 그림만으로도 구현의 방법이 그려졌을 것이다.

트라이의 구현에서는 다음과 같은 기능이 필요하다.

 

(1) 해당 단어가 존재하는지 판단하는 기능 (find)

위의 그림에서, 'trim'을 찾는 과정을 생각해보자.

루트 노드에서 't'를 찾아가고, 그 하위 노드인 'r'을 찾아가고, 'i'와 'm'을 찾아 들어간다.

만약 트라이에 없는 단어, 예를 들어 'love'를 찾는다면 하위 노드로 들어갈 수 없기 때문에 판단이 용이하다.

그렇다면 'tri'가 삽입된 단어인지 아닌지는 판단은 어떻게 할까?

각 노드마다 boolean 타입의 값을 갖게 하고, 이 노드가 'true'라면 해당 노드까지의 단어가 삽입된 것으로 판단한다.

 

(2) 특정 단어를 삽입하는 기능 (insert)

삽입하려는 각 단어마다 하위 노드에 존재하는지 판단하고, 없다면 새로 만들어주고 있다면 하위 노드로 진입한다.

이 과정을 반복함으로써 트라이가 구성된다.

 

 

 

 

 

 

트라이의 구현 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

class Node
{
public:
	Node* childs[26] = { NULL };
	bool isWord = false;

	Node() {}
};

class Trie
{
public:
	Node* root;

	Trie() { this->root = new Node(); }

	void insert(const char* str)
	{
		Node* cur = this->root;

		for (int i = 0; i < strlen(str); i++)
		{

			if (cur->childs[str[i] - 'a'] != NULL) cur = cur->childs[str[i] - 'a'];
			else
			{
				cur->childs[str[i] - 'a'] = new Node();
				cur = cur->childs[str[i] - 'a'];
			}
		}

		cur->isWord = true;
	}

	bool find(const char* str)
	{
		Node* cur = this->root;

		for (int i = 0; i < strlen(str); i++)
		{
			if (cur->childs[str[i] - 'a'] == NULL) return 0;
			else cur = cur->childs[str[i] - 'a'];
		}

		if (cur->isWord) return 1;
		else return 0;
	}
};

int main(void)
{
	Trie trie;

	trie.insert("tree");

	cout << trie.find("tree") << '\n';
	cout << trie.find("tre") << '\n';

	return 0;
}