[자료구조] Trie 트라이

Trie는 ?

• 저장된 문자열을 효과적으로 탐색할 수 있는 자료구조
• 트리 구조
• 시간 복잡도 O(N) : N은 문자열의 길이
• prefix tree, radix tree, retrieval tree 등으로 부름
• 단점 : 거대한 공간 복잡도

trie는 문자열 탐색에 굉장히 유용한 자료구조이다

문자열이 주어지게되면 문자를 저장하는 노드를 하나씩 생성해가면서 트리구조를 만든다

자동으로 정렬된 효과를 볼수 있다는 장점도 있다

 

예시

root 노드는 가장 상위 노드를 의미한다

"ALCUK" "EZ" "EZYUN" "EZYOON" 4글자를 넣은 Trie 트리 모양

 

 

구현

- 간단한 기본 코드

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int ptr_num = 10;

struct Trie {
	bool finish;

	//다음 노드를 가리키는 포인터 배열
	Trie* child[ptr_num];

	//생성자 : 포인터 배열 및 변수 초기화
	Trie() {
		fill(child, child + ptr_num, nullptr);
		finish = false;
	}

	//소멸자 for 메모리 관리
	~Trie() {
		for (int i = 0; i < ptr_num; i++) if (child[i]) delete child[i];
	}

	//문자 삽입
	void insert(char* key) {
		if (*key == NULL) {
			finish = true; //문자열이 끝났을 때 끝을 표시하고 끝내기
			return;
		}
		else {
			int cur = *key - 'A';
			if (!child[cur]) child[cur] = new Trie; //자식노드가 없다면 만들기
			child[cur]->insert(key + 1); //자식노드로 보내 이어서 insert
		}
	}

	//문자 탐색
	bool find(char* key) {
		if (*key == NULL) {
			if (finish = true) return true;
			return false;
		}
		else {
			int cur = *key - 'A';
			if (child[cur] == NULL) return false;
			return child[cur]->find(key + 1); //자식노드로 보내 이어서 find
		}
	}
};