삽입
Coddy의 트라이 - 자료구조 시리즈 #8 코스 레슨 — 14개 중 5번째.
트라이(trie)에 단어를 삽입하려면 루트에서부터 한 번에 한 문자씩 아래로 내려갑니다. 단어의 각 문자에 대해: 현재 노드에 해당 문자에 대한 자식 노드가 없으면, 새로운 TrieNode를 생성하고 연결합니다. 어느 경우든, 해당 자식 노드로 이동하여 다음 문자를 계속 진행합니다.
단어의 끝에 도달하면, 도착한 노드에 isEndOfWord = true로 표시합니다. 이 플래그는 나중에 실제 저장된 단어와 다른 단어의 접두사이기 때문에 우연히 존재하는 경로를 구분해 주는 역할을 합니다.
"cat"을 삽입한 후 "car"를 삽입하면 c -> a 경로를 공유하며 세 번째 문자에서만 갈라집니다. 이러한 공유 덕분에 트라이는 사전 데이터에 대해 매우 공간 효율적입니다.
챌린지
쉬움Trie 클래스에 insert 메서드를 추가하세요.
이 메서드는 문자열 word를 받아서 트라이(trie)에 저장합니다:
root에서 시작합니다.word의 각 문자c에 대해, 현재 노드에c를 위한 자식 노드가 없다면 그곳에 새로운TrieNode를 추가합니다.- 해당 자식 노드로 이동하여 계속 진행합니다.
- 마지막 문자까지 처리한 후, 최종 노드의
isEndOfWord를true로 설정합니다.
직접 해보기
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}