Trie 자료 구조

우리나라 발음으로 트리에 인줄 알았는데, 트라이 라고 함 ㅎㅎ.

Trie 자료 구조

Trie 자료 구조는 string으로 인덱싱 할 수 있는 Look Up 자료 구조의 형태이다. 이는 사전식 순서로 데이터를 저장하거나 string을 탐색하는데 효율적인 방식으로 문장이나 단어 예측 및 자동 완성, 스펠 체크 등에 사용된다.

 

Trie 자료 구조는 Tree 형태의 자료 구조로 digital tree, prefix tree 라고도 불린다. 주로 string을 저장하는데 사용되며 Tree Node는 각 character를 저장한다. 모든 자식 노드는 공통된 prefix string의 부모 노드들을 가지고, root 노드는 empty string이다. (이렇게 prefix로 접근해 데이터를 접근하는 방식이 메모리를 최적화 한다.) 값을 저장하거나 변경하거나 삭제 연산을 수행하기 위해선 Trie 자료 구조를 Depth-First Search로 순회한다.

출처 : 위키백과

Trie 자료 구조를 설명하는 위키 백과에는 위와 같은 그림이 있다. 좀 잘못됐는데, 우선 각 Node는 문자를 저장하고 있는 것은 아니다. DFS로 탐색 시 Child Node가 저장된 배열 인덱스를 통해 해당 문자를 알 수 있을 뿐이다. 그리고 하나의 Node는 한개의 Character만 가리킨다. 따라서 Depth 1의 가장 왼쪽 t의 자식 노드들은 각각 to와 te를 가리키는 것이 아닌 o와 e를 가리킨다.

연산

Trie 자료구조는 Search(+ StartWith), Insert, Delete 연산을 수행한다.

1. Search : Trie 자료구조에 특정 string이 저장되어 있는지 확인한다. StartWith은 특정 string이 prefix로 저장되어 있는지 확인하는 것이다. (ex/ Trie 자료구조에 Apple이 저장된 경우, Search(App) -> false, StartWith(App) -> true)
2. Insert : Trie 자료구조에 특정 string을 저장한다.
3. Delete Trie 자료 구조에 특정 string을 삭제한다.

위 3가지 연산의 Time Complexity는 모두 O(n)이다.

참고 문제

• 사전식 순서로 데이터 저장 : LeetCode 386. Lexicographical Numbers
• Trie 자료 구조 구현(Search, Insert) : LeetCode 208. Implement Trie (Prefix Tree)

구현

#include <string>

using namespace std;

class TrieNode {
public:
	TrieNode* child[27];
	bool IsTerminal;

	TrieNode() {
		IsTerminal = false;
		for (auto& a : child) a = nullptr;
	}
};

class Trie {
	TrieNode* root;
	const int ASCIITrsfNumber = 97;

public:
	Trie() {
		root = new TrieNode();
	}

	void insert(string word) {
		TrieNode* SearchNode = root;
		int idx = 0;

		for (int i = 0; i != word.length(); ++i)
		{
			idx = (int)word[i] - ASCIITrsfNumber;

			if (SearchNode->child[idx] == nullptr)
			{
				SearchNode->child[idx] = new TrieNode();
			}
			else
			{
				// Do Nothing
			}

			SearchNode = SearchNode->child[idx];
		}

		SearchNode->IsTerminal = true;
	}

	bool search(string word, bool prefix = false) {
		bool Retval = true;
		TrieNode* SearchNode = root;
		int idx = 0;

		for (int i = 0; i != word.length(); ++i)
		{
			idx = (int)word[i] - ASCIITrsfNumber;

			if (SearchNode->child[idx] == nullptr)
			{
				Retval = false;
				break;
			}
			else
			{
				SearchNode = SearchNode->child[idx];
			}
		}

		if ((prefix == false) && (Retval == true) && (SearchNode->IsTerminal == false))
		{
			Retval = false;
		}
		else
		{
			// Do Nothing
		}

		return Retval;
	}

	bool startsWith(string prefix) {
		return search(prefix, true);
	}
};