트라이 (Trie)

트라이 (Trie) 자료구조

트라이 자료구조는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다

 

- 트라이의 형태

Node 안의 글자가 안보이면 이미지를 클릭하세요

 

-예시 코드

class Node
{
public:
	Node* childs[26];
	bool isEnd = false;

	Node()
	{
		fill(childs, childs + 26, nullptr);
	}

	void insert(const char* key)
	{
		if (*key == 0) {
			isEnd = true;
			return;
		}

		int nextID = *key - 'a';
		if (childs[nextID] == nullptr)
			childs[nextID] = new Node();

		childs[nextID]->insert(key + 1);
	}

	Node* find(const char* key)
	{
		if (*key == 0)
			return this;

		int nextID = *key - 'a';
	
		if (childs[nextID] == nullptr) 
			return nullptr;

		return childs[nextID]->find(key + 1); 
		
	}
};

 

-Trie 자료구조 사용 부분

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	Node* root = new Node();

	while (N--)
	{
		char text[501];
		cin >> text;
		root->insert(text);
	}

	int count = 0;

	while (M--)
	{
		char text[501];
		cin >> text;
		Node* node = root->find(text);
		if (node && node->isEnd)
			count++;
			
		
	}
	cout << count << "\n";

}

 

 

1. Insert 함수를 이용하여 트라이 자료구조에 문자를 채워 넣음 (문자를 index로 변환하여 해당 index에 Node 생성)

2. find 함수로 찾고자 하는 문자열을 보냄

3. 문자를 Index로 바꾸고 해당 Index 위치에 Node가 생성되어 있는지 체크

4. 모든 문자의 확인이 끝났다면 반환

5. 노드의 isEnd변수가 true라면 count++