Quick Reference
| 연산 | 비용 | 기준 |
|---|---|---|
| insert | O(L) | 문자열 길이 L |
| search word | O(L) | 끝 표시까지 확인 |
| search prefix | O(L) | prefix 경로만 확인 |
| enumerate | O(방문 노드 + 반환 단어 길이 합) | prefix를 공유하는 단어 나열 |
sealed class TrieNode
{
public Dictionary<char, TrieNode> Next { get; } = new();
public bool IsWord { get; set; }
}문자열 전체 존재만 보면 HashSet<string>이 더 단순합니다. 같은 prefix를 공유하는 단어를 찾거나 자동완성 후보를 순회할 때 Trie를 고릅니다. Dictionary<char, TrieNode>는 sparse한 문자 집합에, 고정된 작은 알파벳 배열은 예측 가능한 성능에 맞습니다.
구조
Trie는 문자열 전체를 하나의 키로 저장하지 않고, 각 문자를 노드 간 경로로 저장합니다. 같은 prefix를 가진 단어들은 앞쪽 노드를 공유합니다.
cat
car
care
c
└─ a
├─ t*
└─ r*
└─ e**는 단어가 끝나는 위치입니다. prefix 경로가 존재한다고 해서 그 prefix 자체가 단어라는 뜻은 아닙니다. 예를 들어 car가 단어인지 여부는 r 노드의 IsWord로 판단합니다.
삽입과 조회
삽입은 문자를 하나씩 따라가며 없는 노드를 만들고, 마지막 노드에 단어 종료 표시를 남깁니다.
void Insert(TrieNode root, string word)
{
TrieNode node = root;
foreach (char ch in word)
{
if (!node.Next.TryGetValue(ch, out TrieNode? next))
{
next = new TrieNode();
node.Next[ch] = next;
}
node = next;
}
node.IsWord = true;
}조회는 같은 경로를 따라가되, 단어 검색이면 마지막에 IsWord가 true인지 확인하고, prefix 검색이면 경로 존재만 확인합니다.
static TrieNode? FindNode(TrieNode root, string text)
{
TrieNode node = root;
foreach (char ch in text)
{
if (!node.Next.TryGetValue(ch, out TrieNode? next)) return null;
node = next;
}
return node;
}
static bool Contains(TrieNode root, string word) => FindNode(root, word)?.IsWord == true;
static bool HasPrefix(TrieNode root, string prefix) => FindNode(root, prefix) is not null;
static bool RemoveWord(TrieNode root, string word)
{
TrieNode? node = FindNode(root, word);
if (node is null || !node.IsWord) return false;
node.IsWord = false; // lazy deletion: 공유 경로와 노드는 남긴다.
return true;
}빈 문자열을 Insert하면 root의 IsWord가 true가 됩니다. 따라서 위 API에서 빈 문자열은 저장한 적이 있으면 단어이고, 빈 prefix는 언제나 존재합니다. RemoveWord는 단어 끝 표시만 지우므로 메모리를 즉시 줄이지 않습니다. 노드를 회수하려면 삭제 뒤 자식이 없고 IsWord도 false인 노드만 아래에서 위로 제거해야 합니다.
prefix 후보 나열
using System.Text;
static IEnumerable<string> Enumerate(TrieNode root, string prefix)
{
TrieNode? start = FindNode(root, prefix);
if (start is null) yield break;
var buffer = new StringBuilder(prefix);
foreach (string word in EnumerateFrom(start, buffer)) yield return word;
}
static IEnumerable<string> EnumerateFrom(TrieNode node, StringBuilder buffer)
{
if (node.IsWord) yield return buffer.ToString();
foreach (KeyValuePair<char, TrieNode> pair in node.Next)
{
buffer.Append(pair.Key);
foreach (string word in EnumerateFrom(pair.Value, buffer)) yield return word;
buffer.Length--;
}
}후보 개수와 각 후보 길이만큼은 결국 읽어야 합니다. Dictionary 순회 순서는 자동완성의 표시 순서 계약으로 삼지 말고, 빈도·점수·사전순이 필요하면 결과를 별도 정렬하거나 노드에 우선순위 정보를 둡니다.
선택 기준
| 상황 | 선택 |
|---|---|
| prefix로 시작하는 단어를 자주 찾음 | Trie |
| 전체 문자열 존재 여부만 확인 | HashSet<string> |
| 정렬된 문자열 목록에서 prefix 범위 탐색 | 정렬 + binary search |
| 알파벳 범위가 작고 성능이 중요 | 배열 children |
| 문자 종류가 넓거나 sparse함 | Dictionary<char, TrieNode> |
Trie의 시간 복잡도는 단어 개수보다 문자열 길이에 직접 묶입니다. 단어가 많아도 prefix 길이만큼만 내려가면 후보 영역에 도달할 수 있습니다.
주의할 점
Trie는 노드를 많이 만들기 때문에 메모리를 많이 쓸 수 있습니다. 단어 수가 적거나 단순 존재 검사만 필요하면 HashSet<string>이 더 단순하고 빠를 수 있습니다.
이 구현의 char와 string.Length는 UTF-16 code unit 기준입니다. BMP 밖의 이모지(emoji)는 두 char가 될 수 있고, 조합된 글자는 여러 code unit일 수 있습니다. 사용자 인식 글자 단위가 필요하면 text element나 별도 token 열을 키로 삼도록 노드 구조부터 바꿔야 합니다.
참고 링크
1 sources