Trie

문자열 탐색에 최적화된 트리구조의 자료구조

 

문자열의 접두사(Prefix)를 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다.

자동완성 및 사전 검색에 특화되어 있다.

 

k진 트리이다

즉 어떤 문자열이 저장되어있는지에 따라 달라진다

 

이건 처음부터 어떤 형태로 존재하는 자료구조가 아닌 

데이터가 들어오면서 만들어지는 자료구조임

 

노드로 구성되어 있고 각 노드는 다음과 같음.

typedef struct _Node {
	struct _Node* childs[26] = { NULL, };
	bool isWord = false;
}Node;

 

각 노드는 26개의 자식노드들을 가질 수 있는

각 알파벳을 상징하는 노드들에 대한 포인터를 가질 수 있는 자식 노드 구조를 가짐

 

이 특정 노드는 한 개의 문자를 대변하고

Node* childs[26] 배열은 해당 문자 다음에 오는 문자를 저장함

정확히 말하면 다음에 오는 문자를 대변하는 노드의 주소를 저장

 

isWord는 특정 노드까지가 특정 단어의 완성이면 true가 됨

그래서 문자열을 검색할때 만약 isWord가 true인 노드가 있으면

거기까지 잘 왔다는 뜻이므로 해당 문자열이 존재한다는거임.

사실 이 글을 쓰면서도

트라이가 자료구조를 말하는건지 이 알고리즘 자체를 말하는건지는 모르겠다

 

근데 어차피 그냥 문제만 풀 수 있으면 됨 ㅇㅇ

 

---

[트라이에 문자열 반영하기]

 

구현할때 Node* root 만 미리 생성해두고 

insert의 인자로 새로운 문자열을 줘서 트라이에 반영해주면 된다.

 

string 을 순회하며

1) 이미 생성되어있는 노드를 따라가거나

2) 필요한 노드를 동적할당으로 생성하며

트리를 만들어감

 

맨 마지막에는 단어의 끝임을 알려주는 isWord = true 처리로 끝냄

 

// 트라이 추가 함수
void insert(Node* root, string s) {
	Node* cur = root;

	int idx;
	for (int i = 0; i < s.size(); i++) {
		idx = s[i] - 'a';

		if (cur->childs[idx] == NULL) {
			cur->childs[idx] = new Node();
		}

		cur = cur->childs[idx];
	}

	cur->isWord = true;
}

 

---

[문자열 포함관계 여부 확인]

 

중복확인을 하려면 무조건 긴 문자열보다 짧은 문자열이 트라이에 먼저 반영되어야함

 

그래서 문자열 길이를 기준으로 오름차순으로 정렬한 뒤, 짧은 것부터 순서대로 트라이에 반영하면서

경로에 isWord = True 인지를 확인해가며 문자열들간의 포함관계 여부를 확인할 수 있다.

 

// 트라이 추가 함수
bool insert(Node* root, string s) {
	Node* cur = root;

	int idx;
	for (int i = 0; i < s.size(); i++) {
		idx = s[i] - '0';

		if (cur->childs[idx] == NULL) {
			cur->childs[idx] = new Node();
		}

		cur = cur->childs[idx];
		// 가던 길에 단어인 놈이 있으면 일관성 없는거임
		if (cur->isWord) {
			return false;
		}
	}

	cur->isWord = true;

	return true;
}