문자열 탐색 자료구조 - 트라이(Trie)

트라이(Trie)

 

 

트라이란?

 

 - 문자열의 집합을 관리하는 자료구조.

 

 - 문자열을 빠르게 탐색할 수 있게 도와주는 자료구조.

 

 - 탐색하려는 문자를 O(n)의 시간복잡도로 구할 수 있다.(n은 문자열의 길이)

 

 - 트라이는 시간 복잡도 측면에서 강점을 가지지만, 공간 복잡도 측면에서는 단점을 가진다.

 

---

 

트라이 작동 방법

 

 - 1. 탐색하려는 문자열의 문자들을 순차적으로 접근한다.

 

 - 2. 해당 문자들이 노드에 있는 지 확인한다.

 

 - 3. 해당 문자들이 노드에 존재하지 않는다면, 새로 추가한다.

 

 - 4. 문자의 마지막에 해당하는 노드에는 마지막이라는 표시를 해준다.

 

- 트라이 자료구조에서 cake 라는 단어를 탐색.

 

 

 

- root노드와 연결된 노드 중 cake의 첫 번째 문자인 c가 있는지 탐색 후 방문

 

 

 

- c노드와 연결된 노드 중 cake의 두 번째 문자인 a가 있는지 탐색 후 방문

 

 

 

 

- a노드와 연결된 노드 중 cake의 세 번째 문자인 k가 있는지 탐색 후 방문

- k노드와 연결된 노드 중 cake의 세 번째 문자인 e가 있는지 탐색 후 방문

- 4번의 탐색으로 cake라는 문자가 저장되어 있는지 탐색할 수 있다.

---

 

 

 

트라이 코드(C++)

#include <bits/stdc++.h>
#include <string>

using namespace std;

struct Trie
{
	// 알파벳 26자
	Trie *childNode[26];
	bool isFinish;

	Trie()
	{
		isFinish = false;
		for (int i = 0; i < 26; i++)
			childNode[i] = NULL;
	}

	~Trie()
	{
		for (int i = 0; i < 26; i++)
		{
			// childNode[i] == NULL == 0
			// NULL이 아닌 값은 데이터 삭제
			if (childNode[i])
				delete childNode[i];
		}
	}

	void insert(string& str, int i)
	{
    	// 문자열 끝인 경우
		if (str.size() == i)
		{
			isFinish = true;

		}
		else
		{
			int nextNode = str[i] - 'A';
			if (childNode[nextNode] == NULL)
			{
				childNode[nextNode] = new Trie();
			}
			childNode[nextNode]->insert(str, i + 1);
		}
	}

	bool find(string& str,int i)
	{
		// 해당 문자가 기존의 트라이에 있는지 판단.
		// abc라는 문자만 트라이에 있고, ab를 탐색할 때 해당 노드는 
		// 트라이에 없기 때문에 isFinish(false) 출력
		if (str.size() == i)
		{
			return isFinish;
		}
		
		int nextNode = str[i] - 'A';

		if (childNode[nextNode] == NULL)
			return false;

		return childNode[nextNode]->find(str,i+1);
	}
};

 

 

트라이 활용 문제

 

 

[BOJ-5052] 전화번호 목록 (C++)