trie
자동완성 등에 특화된 자료구조
-> 접두사를 기준으로 빠른 탐색 가능
그냥 배열 vs trie
- 단어 탐색: N개의 단어가 있을 때 L길이의 단어를 찾는다면
배열: N개의 단어에 대해 L길이만큼 다 맞는지 확인 -> O(LN)
trie: 단어 길이만큼만 분기를 따라가면 됨 -> O(L) - 접두사 탐색: P길이의 접두사가 주어지고 N개의 단어 중 찾는다면
배열: P길이의 접두사 비교를 N개의 단어에 대해 모두 확인 -> O(PN)
trie: 얘도 접두사 만큼만 따라가면 됨 -> O(P) (= O(L)) - 메모리 차지
배열은 그냥 저장하면 되지만
trie는 노드별로 분기를 저장해야 되기 때문
예) 영어를 저장하는 trie는 각 노드마다 26개의 공간이 있어야 한다.
<- 물론 자식이 생길 때마다 포인터 공간을 동적할당하는 경우도 있는데 전통적인 trie에선 아님 - 이식성
당연히 배열이 훨-씬 쉬움
구현
기본 골조
이진트리랑 다르게 자식을 가리키는 포인터가 (영어 기준)26개나 된다.
그리고 isEndOfWord라는 값이 추가로 더 필요하다.
왜냐하면 접두사가 같은 다른 단어를 저장할 때 그 단어인지 판별하기 위해서이다.
예) car와 care이 저장되었다 하자.
c - a - r - e
이게 care 한 글자인지 car, care 두 글자인지 ca, car, care인지 끝이 지정되지 않았으면 알지 못함.
따라서 r, e에 isEndOfWord로 표시를 해줘야 한다.
#define ALPHABET_SIZE 26
typedef struct TrieNode{
struct TriNode* children[ALPHABET_SIZE];
bool isEndOfWord;
} TrieNode;
makeTrieNode
빈 TrieNode를 만든다.
TrieNode* makeTrieNode(){
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++){
node->children[i] = NULL;
}
return node;
}
search
글자 하나하나 따라가며
글자가 있는가?
있긴 한데 그게 글자의 끝인가?
를 따짐
bool search(TrieNode* root, const char* word){
TrieNode* curr = root;
for (int i = 0; word[i] != '\0'; i++){ //글자 하나하나 따라가겠다는 뜻
int index = word[i] - 'a';
if (curr->children[index] == NULL) {return false;} //만약 따라갔는데 없다면?
curr = curr->children[index]; //다음 글자로 이동
}
return curr->isEndOfWord; // 해당 글자가 있는가? & 글자의 끝인가? 체크
}
insert
단어의 한 글자씩 노드를 추가한다.
void insert(TrieNode** root, const char* word){
TrieNode* curr = root;
for (int i = 0; word[i] != '\0'; i++){ //단어의 끝까지 반복
int index = word[i] - 'a'; //'a'를 빼서 문자를 인덱스로 바꾸기
if (curr->children[index] == NULL){
curr->children[index] = makeNode();
}
curr = curr->children[index];
}
curr->isEndOfWord = true; //마지막에 isEndOfWord를 true로 바꿔 마무리
}
delete
먼저 비어있는지 확인 후
bool isEmpty(TrieNode* root){
for (int i = 0; i < ALPHABET_SIZE; i++){
if (root->children[i]) {return false;}
}
return true;
}
지운다.
TrieNode* deleteWord(TrieNode* root, const char* word, int depth = 0){
if (!root) {return NULL;} // 없는 경로면 바로 빠져나감
if (word[depth] == '\0'){ // 단어의 끝인가?
if (root->isEndOfWord) {root->EndOfWord = false} //단어의 끝을 해제하는 것으로 단어 지우기는 끝남
if (isEmpty(root)){ //아무것도 없으면 바로 free
free(root);
return NULL;
}
return root;
}
// 만약 뒤에 단어가 더 남았으면
int index = word[depth] - 'a';
root->children[index] = delete(root->children[index], word, depth + 1);//재귀호출로 계속 지우기
if (isEmpty(root) && !root->isEndOfWord){
free(root);
return NULL;
}
return root;
}
728x90
반응형
'CS > 자료구조' 카테고리의 다른 글
[자료구조](19)[해시 테이블] (0) | 2025.05.22 |
---|---|
[자료구조](18)[map & 해시함수] (0) | 2025.05.21 |
[자료구조](16)[힙 구현] (0) | 2025.05.19 |
[자료구조](-)[힙 생성의 시간복잡도는 O(n)?] (0) | 2025.05.15 |
[자료구조](15)[우선순위 큐 & 힙] (0) | 2025.05.14 |