트라이

N개의 정수나 실수로 이루어진 한 집합에서 특정 수를 찾는 것은 이진 탐색 트리에서 O(logN)의 시간이 소요됩니다.

하지만 집합이 문자열로 이루어져 있다면, M의 길이를 갖는 문자열을 탐색할 땐 O(M*logN)이 걸릴 것입니다.

 

트라이(Trie) 자료구조에서는 문자열 집합에서 특정 문자열이 존재하는지 O(M)만에 알 수 있습니다.

---

트라이

문자열 TABLE, TABLET, TAIWAN, TREE, TRIE, PHONE이 들어있는 문자열 집합을 생각해 봅시다.

문자열 집합에 속한 문자열들은 모두 대문자 알파벳으로 구성되어 있다고 가정하겠습니다.

 

일반적인 이진 탐색 트리라면 사전 상에서 앞에 있는 문자열이 왼쪽, 뒤에 있는 문자열이 오른쪽이 배치될 것입니다.

 

트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.

 

트라이의 한 노드는 자식 노드를 가리키는 포인터와, 루트 노드부터 해당 노드까지의 문자들을 갖는 문자열이 집합에 있는지 나타내는 Boolean 변수로 구성되어 있습니다.

각 노드는 알파벳 대문자의 개수 26개만큼의 포인터를 가지고 있으며, 가리킬 글자가 없으면 NULL을 가리키게 됩니다.

 

노드의 수 만큼 26개의 포인터를 갖기 때문에 메모리를 많이 잡아먹지만, 덕분에 빠른 시간 안에 탐색할 수 있습니다.

 

---

구현

 

struct TrieNode {
	TrieNode* son[26];
	bool terminal;
	TrieNode() : terminal(false) {
		memset(son, 0, sizeof(son));
	}
	~TrieNode() {
		for (int i = 0;i < 26;i++) if (son[i]) delete son[i];
	}
	void insert(const char* key) { //문자열 삽입
		if (*key == '\0') terminal = true;
		else {
			int curr = *key - 'A';
			if (son[curr] == NULL) son[curr] = new TrieNode();
			son[curr]->insert(key + 1);
		}
	}

	TrieNode* find(const char* key) { //문자열 탐색
		if (*key == '\0') return this;
		int curr = *key - 'A'; 
		if (son[curr] == NULL) return NULL;
		return son[curr]->find(key + 1);
	}
};

 

---