[자료구조] 트라이 (Trie)

트라이 (Trie) 란?

• 문자열을 저장하고, 효율적으로 탐색하기 위한 트리 형태의 자료구조

• tree 형태의 자료구조
• 정보 검색 같은 분야에서 활용된다.
• 위와 같은 그림처럼 빠르게 단어를 찾는 것에 효율적으로 동작할 수 있다.

 

장단점

장점

• 문자열 검색에 효율적이며, 접두사 검색을 O(m) 시간에 수행 가능 (m은 문자열 길이).
• 자동 완성 기능 구현에 유용.

단점

• 많은 메모리를 사용하며, 자식 노드가 많아질수록 성능이 저하될 수 있음.

구현

class TrieNode를 사용한 구현

#include <iostream>
#include <string>
#include <vector>

class TrieNode
{
private:
public:
	TrieNode *child[26];
	bool wordEnd;

	TrieNode() {
		wordEnd = false;
		for(int i = 0; i < 26; i++) {
			child[i] = NULL;
		}
	}
	~TrieNode() {};
};

// trie에 데이터 삽입
void insertKey(TrieNode* root, const std::string& key) {

	TrieNode* curr = root;

	// root를 계속 변경하면서 데이터 추가 ( ex: abc : a->b->c )
	for (char c : key) {
		if (curr->child[c - 'a'] == nullptr) {
			TrieNode* newNode = new TrieNode();
			curr->child[c - 'a'] = newNode;
		}
		curr = curr->child[c - 'a'];
	}
	curr->wordEnd = true;
}

// trie에 데이터 검색
bool searchKey(TrieNode* root, const std::string& key) {
	
	TrieNode* curr = root;

	for (char c: key) {
		if (curr->child[c - 'a'] == nullptr)
			return false;
		curr = curr->child[c - 'a'];
	}
	return curr->wordEnd;
}

int main() {

	TrieNode* root = new TrieNode();

	std::vector<std::string> arr = {"abc", "abd", "abe", "abf"};
	for (const std::string& s : arr) {
		insertKey(root, s);
	}
	std::vector<std::string> searchKeys = {"abc", "abd", "abe", "abf", "abg", "abh"};
	for (std::string& s : searchKeys) {
		std::cout << "Key : " << s << "\n";
		if (searchKey(root, s)) 
			std::cout << "Present" << "\n";
		else 
			std::cout << "Not Present" << "\n";
	}
  
	return 0;
}

• 원하는 문자가 TrieNode안에 있는지 시간 복잡도: O(단어 수 * maxLengthOfWord), 보조 공간: O(단어 수 * maxLengthOfWord) 으로 빠르게 찾는것이 가능하다.

 

참고자료

https://www.geeksforgeeks.org/trie-insert-and-search/